AtCoder Daily Training EASY 2024/05/21 15:30start

A - First ABC 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる長さ N の文字列 S が与えられます。
S の中で ABC が(連続な)部分文字列として初めて現れる位置を答えてください。すなわち、以下の条件を全て満たす整数 n のうち最小のものを答えてください。

1 \leq n \leq N - 2
S の n 文字目から n+2 文字目までを取り出して出来る文字列は ABC である。

ただし、ABC が S に現れない場合は -1 を出力してください。

制約

3 \leq N \leq 100
S は A, B, C からなる長さ N の文字列

入力

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

N
S

出力

S の中で ABC が部分文字列として初めて現れる位置を出力せよ。ただし、ABC が S に現れない場合は -1 を出力せよ。

入力例 1

8
ABABCABC

出力例 1

S の中で ABC が初めて現れるのは 3 文字目から 5 文字目までの位置です。よって 3 が答えになります。

入力例 2

3
ACB

出力例 2

-1

ABC が S に現れない場合は -1 を出力してください。

入力例 3

20
BBAAABBACAACABCBABAB

出力例 3

Score : 100 points

Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

1 \leq n \leq N - 2.
The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

3 \leq N \leq 100
S is a string of length N consisting of A, B, and C.

Input

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

N
S

Output

Print the position where ABC first appears as a substring in S, or -1 if it does not appear in S.

Sample Input 1

8
ABABCABC

Sample Output 1

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

B - QQ solver

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

3 文字からなる文字列 S が与えられます。S は、1 以上 9 以下の整数 a, b と文字 x を、axb のように順につなげて得られます。

a と b の積を求めてください。

制約

S の長さは 3
S の 1 文字目および 3 文字目は 1 以上 9 以下の整数を表す
S の 2 文字目は x

入力

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

出力

答えを出力せよ。

入力例 1

3x7

出力例 1

3 \times 7 = 21 であるので、これを出力します。

入力例 2

9x9

出力例 2

入力例 3

1x1

出力例 3

Score : 100 points

Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

The length of S is 3.
The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
The 2-nd character is x.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

3x7

Sample Output 1

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

Sample Input 3

1x1

Sample Output 3

C - Minimize Abs 1

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

L\leq X_i \leq R
L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

L\leq X_i \leq R.
For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
All input values are integers.

Input

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

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

D - 1D Pawn

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。 i 回目の操作では次の操作を行います。

左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。

Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。

制約

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
入力はすべて整数

入力

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

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

出力

K 個の整数を空白区切りで一行に出力せよ。ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。

入力例 1

5 3 5
1 3 4
3 3 1 1 2

出力例 1

2 4 5

最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。

左から 3 番目のコマはマス 4 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。コマはマス 1, 3, 5 にある状態になります。
左から 3 番目のコマはマス 5 にあります。これは一番右のマスなので、何も行いません。コマはマス 1, 3, 5 にある状態のままです。
左から 1 番目のコマはマス 1 にあります。これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。コマはマス 2, 3, 5 にある状態になります。
左から 1 番目のコマはマス 2 にあります。これは一番右のマスでありませんが、その 1 つ右のマス（マス 3 ）にコマが置かれているため、何も行いません。コマはマス 2, 3, 5 にある状態のままです。
左から 2 番目のコマはマス 3 にあります。これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。コマはマス 2, 4, 5 にある状態になります。

よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。

入力例 2

2 2 2
1 2
1 2

出力例 2

1 2

入力例 3

10 6 9
1 3 5 7 8 9
1 2 3 4 5 6 5 6 2

出力例 3

2 5 6 7 9 10

Score : 200 points

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

If the L_i-th piece from the left is on its rightmost square, do nothing.
Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

1\leq K\leq N\leq 200
1\leq A_1<A_2<\cdots<A_K\leq N
1\leq Q\leq 1000
1\leq L_i\leq K
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

Output

Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

10 6 9
1 3 5 7 8 9
1 2 3 4 5 6 5 6 2

Sample Output 3

2 5 6 7 9 10

E - Max MEX

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

長さ N の非負整数列 A が与えられます。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、 MEX(B) としてありえる最大値を求めてください。

但し、数列 X に対して MEX(X) は以下の条件を満たす唯一の非負整数 m として定義されます。

0 \le i < m を満たす全ての整数 i が X に含まれる。
m が X に含まれない。

制約

入力は全て整数
1 \le K \le N \le 3 \times 10^5
0 \le A_i \le 10^9

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

7 3
2 0 2 3 2 1 9

出力例 1

この入力では A=(2,0,2,3,2,1,9) であり、ここから K=3 要素を選んで抜き出して数列 B を得ます。例えば、

1,2,3 要素目を抜き出した時、 MEX(B)=MEX(2,0,2)=1
3,4,6 要素目を抜き出した時、 MEX(B)=MEX(2,3,1)=0
2,6,7 要素目を抜き出した時、 MEX(B)=MEX(0,1,9)=2
2,3,6 要素目を抜き出した時、 MEX(B)=MEX(0,2,1)=3

のようになります。
達成可能な MEX の最大値は 3 です。

Score : 300 points

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

Every integer i such that 0 \le i < m is contained in X.
m is not contained in X.

Constraints

All values in the input are integers.
1 \le K \le N \le 3 \times 10^5
0 \le A_i \le 10^9

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.