AtCoder Daily Training ALL 2024/02/20 15:30start

A - Middle Letter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる長さが奇数の文字列 S が与えられます。

S の中央の文字を出力してください。

中央の文字とは

ある長さが奇数の文字列 T について、 T の長さを |T| として、T の前から \frac{|T|+1}{2} 番目の文字を中央の文字とします。

制約

S は英小文字からなる長さが奇数の文字列
S の長さは 1 以上 99 以下

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

atcoder の中央の文字は o です。

入力例 2

出力例 2

Score : 100 points

Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

What is the central character?

For an odd-length string T, its central character is the \frac{|T|+1}{2}-th character from the beginning, where |T| is the length of T.

Constraints

S is an odd-length string consisting of lowercase English letters.
The length of S is between 1 and 99 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

The central character of atcoder is o.

Sample Input 2

Sample Output 2

B - To Be Saikyo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N までの番号が付けられた N 人の人がいます。それぞれの人にはプログラミング力という整数値が定まっており、人 i のプログラミング力は P_i です。人 1 が最強になるためには、あといくつプログラミング力を上げる必要がありますか？すなわち、すべての i \neq 1 に対して P_1 + x > P_i を満たすような最小の非負整数 x は何ですか？

制約

1\leq N \leq 100
1\leq P_i \leq 100
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
P_1 P_2 \dots P_N

出力

答えを整数として出力せよ。

入力例 1

4
5 15 2 10

出力例 1

人 1 が最強になるためには、プログラミング力を 16 以上にする必要があります。よって、答えは 16-5=11 です。

入力例 2

4
15 5 2 10

出力例 2

人 1 は既に最強なので、これ以上プログラミング力を上げる必要はありません。

入力例 3

3
100 100 100

出力例 3

Score : 100 points

Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

1\leq N \leq 100
1\leq P_i \leq 100
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \dots P_N

Output

Print the answer as an integer.

Sample Input 1

4
5 15 2 10

Sample Output 1

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

C - Counting Arrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L_i で j (1 \leq j \leq L_i) 番目の要素が a_{i,j} であるような数列です。

数列 i と数列 j は、 L_i = L_j かつすべての k (1 \leq k \leq L_i) に対して a_{i,k} = a_{j,k} が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から数列 N の中に全部で何種類の数列がありますか？

制約

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
すべての数列の要素の個数の和、すなわち \sum_{i=1}^N L_i は 2 \times 10^5 を超えない。
入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

出力

数列の種類数を出力せよ。

入力例 1

出力例 1

入力例 1 で与えられている数列は以下の 4 個です。

数列 1 : (1, 2)
数列 2 : (1, 1)
数列 3 : (2, 1)
数列 4 : (1, 2)

このうち数列 1 と数列 4 は同じ数列で、それ以外は互いに異なる数列なので全部で 3 種類の数列があります。

入力例 2

出力例 2

入力例 2 で与えられている数列は以下の 5 個です。

数列 1 : (1)
数列 2 : (1)
数列 3 : (2)
数列 4 : (1, 1)
数列 5 : (1, 1, 1)

入力例 3

1
1 1

出力例 3

Score : 200 points

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

Output

Print the number of different sequences.

Sample Input 1

Sample Output 1

Sample Input 1 contains four sequences:

Sequence 1 : (1, 2)
Sequence 2 : (1, 1)
Sequence 3 : (2, 1)
Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

Sample Output 2

Sample Input 2 contains five sequences:

Sequence 1 : (1)
Sequence 2 : (1)
Sequence 3 : (2)
Sequence 4 : (1, 1)
Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

D - Split?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ボウリングのピンは 1 から 10 の番号が付けられており、上から見ると下図のように配置されます。

この図の二つの点線に挟まれた部分を列と呼ぶことにします。
例えば、ピン 1, 5 とピン 3, 9 はそれぞれ同じ列に存在します。

いくつかのピンが倒れた状態のうち、特殊なものはスプリットと呼ばれます。
ピンの配置がスプリットであるとは、以下の条件が全て成り立つことを言います。

ピン 1 が倒れている。
ある二つの異なる列であって、次の条件を満たすものが存在する。
- それぞれの列には、立っているピンが 1 本以上存在する。
- それらの列の間に、ピンが全て倒れている列が存在する。

具体例は入出力例を参考にしてください。

さて、あるピンの配置が長さ 10 の文字列 S として与えられます。 i = 1, \dots, 10 について、ピン i が倒れているとき S の i 文字目は 0 であり、ピン i が立っているとき S の i 文字目は 1 です。
S で表されるピンの配置がスプリットかどうか判定してください。

制約

S は 0 と 1 からなる長さ 10 の文字列

入力

入力は以下の形式で標準入力から与えられる。

出力

S で表されるピンの配置がスプリットなら Yes を、そうでないなら No を出力せよ。

入力例 1

0101110101

出力例 1

Yes

倒れているピンを灰色で、立っているピンを白色で示すと下図のようになります。

ex0

ピン 5 が立っている列とピン 6 が立っている列の間にはピン 3, 9 が置かれている列が存在しますが、ピン 3, 9 はいずれも倒れているので、この配置はスプリットです。

入力例 2

0100101001

出力例 2

Yes

ex1

入力例 3

0000100110

出力例 3

No

ex2

この配置はスプリットではありません。

入力例 4

1101110101

出力例 4

No

ex3

ピン 1 が倒れていないので、スプリットではありません。

Score : 200 points

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

Pin 1 is knocked down.
There are two different columns that satisfy both of the following conditions:
- Each of the columns has one or more standing pins.
- There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

S is a string of length 10 consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

Output

If the placement of the pins represented by S is a split, print Yes; otherwise, print No.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

ex0

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

ex1

Sample Input 3

0000100110

Sample Output 3

No

ex2

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

ex3

This is not a split because Pin 1 is not knocked down.

E - Consecutive

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字のみからなる長さ N の文字列 S = S_1S_2\ldots S_N が与えられます。

また、S に関する Q 個の質問が与えられます。 i = 1, 2, \ldots, Q について、i 番目の質問は 2 つの整数 l_i, r_i で表される下記の質問です。

S の l_i 文字目から r_i 文字目までからなる部分文字列 S_{l_i}S_{l_i+1}\ldots S_{r_i} において、同じ英小文字が 2 つ隣りあう箇所は何個ありますか？すなわち、l_i \leq p \leq r_i-1 かつ S_p = S_{p+1}を満たす整数 p は何個ありますか？

Q 個の質問それぞれの答えを出力してください。

制約

N, Q は整数
1 \leq N, Q \leq 3 \times 10^5
S は英小文字のみからなる長さ N の文字列
l_i, r_i は整数
1 \leq l_i \leq r_i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には i 番目の質問に対する答えを出力せよ。

入力例 1

11 4
mississippi
3 9
4 10
4 6
7 7

出力例 1

4 個の質問それぞれに対する答えは下記の通りです。

1 個目の質問に関して、S_3S_4\ldots S_9 = ssissip で同じ英小文字が隣り合う箇所は、S_3S_4 = ss と S_6S_7 = ss の 2 個です。
2 個目の質問に関して、S_4S_5\ldots S_{10} = sissipp で同じ英小文字が隣り合う箇所は、S_6S_7 = ss と S_9S_{10} = pp の 2 個です。
3 個目の質問に関して、S_4S_5S_6 = sis で同じ英小文字が隣り合う箇所は 0 個です。
4 個目の質問に関して、S_7 = s で同じ英小文字が隣り合う箇所は 0 個です。

入力例 2

5 1
aaaaa
1 5

出力例 2

S_1S_2\ldots S_5 = aaaaa で同じ英小文字が隣り合う箇所は、 S_1S_2 = aa 、S_2S_3 = aa 、S_3S_4 = aa 、S_4S_5 = aa の 4 個です。

Score : 300 points

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

N and Q are integers.
1 \leq N, Q \leq 3 \times 10^5
S is a string of length N consisting of lowercase English letters.
l_i and r_i are integers.
1 \leq l_i \leq r_i \leq N

Input

The input is given from Standard Input in the following format:

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the answer to the i-th query.

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

The answers to the four queries are as follows.

For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

F - Merge Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。

長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。

C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
C を昇順にソートする。

A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。

制約

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

出力

答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。

入力例 1

4 3
3 14 15 92
6 53 58

出力例 1

1 3 4 7
2 5 6

C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。

入力例 2

4 4
1 2 3 4
100 200 300 400

出力例 2

1 2 3 4
5 6 7 8

入力例 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

出力例 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Score : 300 points

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

Output

Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

G - Match or Not

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

英小文字と ? からなる文字列 S,T が与えられます。ここで、|S| \gt |T| が成り立ちます(文字列 X に対し、 |X| で X の長さを表します)。

また、|X|=|Y| を満たす文字列 X,Y は、次の条件を満たすとき及びそのときに限りマッチするといいます。

X,Y に含まれる ? をそれぞれ独立に好きな英小文字に置き換えることで X と Y を一致させることができる

x=0,1,\ldots,|T| に対して次の問題を解いてください。

S の先頭の x 文字と末尾の |T|-x 文字を順番を保ったまま連結することで得られる長さ |T| の文字列を S' とする。S' と T がマッチするならば Yes と、そうでなければ No と出力せよ。

制約

S,T は英小文字と ? からなる文字列
1 \leq |T| \lt |S| \leq 3 \times 10^5

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

|T|+1 行出力せよ。
i 行目には x=i-1 に対する出力をせよ。

入力例 1

a?c
b?

出力例 1

Yes
No
No

x=0 の場合、S' は ?c となります。ここで、S' の 1 文字目の ? を b に、T の 2 文字目の ? を c に置き換えることで S' と T を一致させることができるため、S' と T はマッチします。このため、1 行目の出力は Yes です。
x=1,2 の場合は S' はそれぞれ ac、a? であり、T とマッチしません。このため、2,3 行目の出力は No です。

入力例 2

atcoder
?????

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes

入力例 3

beginner
contest

出力例 3

No
No
No
No
No
No
No
No

Score : 400 points

Problem Statement

You are given strings S and T consisting of lowercase English letters and ?. Here, |S| \gt |T| holds (for a string X, |X| denotes the length of X).

Two strings X and Y such that |X|=|Y| is said to match if and only if:

one can make X equal Y by replacing each ? in X and Y with any English letter independently.

Solve the following problem for each x=0,1,\ldots,|T|:

Let S' be the string of length |T| obtained by concatenating the first x characters and the last (|T|-x) characters of S without changing the order. Print Yes if S' and T match, and No otherwise.

Constraints

S and T are strings consisting of lowercase English letters and ?.
1 \leq |T| \lt |S| \leq 3 \times 10^5

Input

The input is given from Standard Input in the following format:

S
T

Output

Print (|T|+1) lines.
The i-th line should contain the answer for x=i-1.

Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When x=0, S' equals ?c. Here, we can replace the 1-st character of S', ?, with b and the 2-nd character of T, ?, with c to make S' equal T, so S' and T match. Thus, Yes should be printed in the first line.
When x=1 and 2, respectively, S' is ac and a?, neither of which matches with T. Thus, No should be printed in the second and third lines.

Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No

H - Lucky Numbers

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N-1 の整数列 S = (S_1, S_2, \ldots, S_{N-1}) および、「ラッキーナンバー」として M 個の相異なる整数 X_1, X_2, \ldots, X_M が与えられます。

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) であって、次の条件を満たすものを「良い数列」と呼びます。

すべての i = 1, 2, \ldots, N-1 について、A_i + A_{i+1} = S_i が成り立つ。

良い数列 A を 1 つ選ぶときの、A の要素のうちラッキーナンバーであるものの個数（すなわち、A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace となる 1 以上 N 以下の整数 i の個数）としてあり得る最大値を求めてください。

制約

2 \leq N \leq 10^5
1 \leq M \leq 10
-10^9 \leq S_i \leq 10^9
-10^9 \leq X_i \leq 10^9
X_1 \lt X_2 \lt \cdots \lt X_M
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
S_1 S_2 \ldots S_{N-1}
X_1 X_2 \ldots X_M

出力

良い数列 A を 1 つ選ぶときの、A の要素のうちラッキーナンバーであるものの個数としてありうる最大値を出力せよ。

入力例 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

出力例 1

良い数列 A として A = (3, -1, 4, -1, 5, -9, 2, -6, 5) を選ぶと、A の要素のうちラッキーナンバーであるものは A_2, A_4, A_5, A_9 の 4 個となり、これが考えられる中で最大です。

入力例 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

出力例 2

Score : 500 points

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 10
-10^9 \leq S_i \leq 10^9
-10^9 \leq X_i \leq 10^9
X_1 \lt X_2 \lt \cdots \lt X_M
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
S_1 S_2 \ldots S_{N-1}
X_1 X_2 \ldots X_M

Output

Print the maximum possible number of terms that are lucky numbers in a good sequence A.

Sample Input 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

Sample Output 1

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.

Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

I - Erase and Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1,2,\ldots,N がちょうど 1 回ずつ現れる数列 P = (p_1,p_2,\ldots,p_N) が与えられます。
あなたは以下の操作のうち 1 つを選んで行うことを 0 回以上 K 回以下繰り返せます。

P の項を 1 つ選び、削除する。
P の末尾の項を先頭に移動させる。

操作後の P として考えられるもののうち辞書順で最小のものを求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq K \leq N-1
1 \leq p_i \leq N
(p_1,p_2,\ldots,p_N) には 1,2,\ldots,N がちょうど 1 回ずつ現れる。
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
p_1 p_2 \ldots p_N

出力

操作後の P として考えられるもののうち辞書順で最小のものを空白区切りで出力せよ。

入力例 1

5 3
4 5 2 3 1

出力例 1

1 2 3

以下のように操作をすると P は (1,2,3) になります。

先頭の項を削除する。これによって P は (5,2,3,1) になる。
末尾の項を先頭に移動させる。これによって P は (1,5,2,3) になる。
先頭から 2 番目の項を削除する。これによって P は (1,2,3) になる。

また、辞書順で (1,2,3) より小さい数列は操作後の P として考えられません。よってこれが答えです。

入力例 2

3 0
3 2 1

出力例 2

3 2 1

操作を 1 回も行えない場合があります。

入力例 3

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

出力例 3

1 3 4 7 2 8 11 9

Score : 500 points

Problem Statement

You are given a sequence P = (p_1,p_2,\ldots,p_N) that contains 1,2,\ldots,N exactly once each.
You may perform the following operations between 0 and K times in total in any order:

Choose one term of P and remove it.
Move the last term of P to the head.

Find the lexicographically smallest P that can be obtained as a result of the operations.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq K \leq N-1
1 \leq p_i \leq N
(p_1,p_2,\ldots,p_N) contains 1,2,\ldots,N exactly once each.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 p_2 \ldots p_N

Output

Print the lexicographically smallest P that can be obtained as a result of the operations, separated by spaces.

Sample Input 1

5 3
4 5 2 3 1

Sample Output 1

1 2 3

The following operations make P equal (1,2,3).

Removing the first term makes P equal (5,2,3,1).
Moving the last term to the head makes P equal (1,5,2,3).
Removing the second term makes P equal (1,2,3).

There is no way to obtain P lexicographically smaller than (1,2,3), so this is the answer.

Sample Input 2

3 0
3 2 1

Sample Output 2

3 2 1

You may be unable to perform operations.

Sample Input 3

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

Sample Output 3

1 3 4 7 2 8 11 9