AtCoder Daily Training MEDIUM 2025/07/23 20:00start

C - Decrease 2 max elements

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。高橋くんは、以下の操作を A に含まれる正の要素の個数が 1 つ以下になるまで繰り返します。

A を要素の降順に並び替える。それから、 A_1, A_2 を 1 減らす。

高橋くんが操作をする回数を求めてください。

制約

2 \leq N \leq 100
1 \leq A_i \leq 100
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4
1 2 3 3

出力例 1

操作は以下のように進みます。

1 回目の操作で A = (2, 2, 2, 1) となる。
2 回目の操作で A = (1, 1, 2, 1) となる。
3 回目の操作で A = (1, 0, 1, 1) となる。
4 回目の操作で A = (0, 0, 1, 0) となる。A に含まれる正の要素の個数が 1 つ以下になったので、ここで操作を終了する。

入力例 2

3
1 1 100

出力例 2

Score : 200 points

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 100
All input values are integers.

Input

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

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4
1 2 3 3

Sample Output 1

The process goes as follows:

After the 1st operation, A is (2, 2, 2, 1).
After the 2nd operation, A is (1, 1, 2, 1).
After the 3rd operation, A is (1, 0, 1, 1).
After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

D - Citation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。次を満たす最大の非負整数 x を求めてください。

A に、 x 以上の要素が重複を含めて x 回以上現れる。

制約

1 \leq N \leq 100
0 \leq A_i \leq 10^9
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
1 2 1

出力例 1

A=(1,2,1) に

0 以上の要素は 3 回
1 以上の要素は 3 回
2 以上の要素は 1 回
3 以上の要素は 0 回

現れます。条件を満たす最大の非負整数は 1 です。

入力例 2

7
1 6 2 10 2 3 2

出力例 2

Score : 200 points

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\dots,A_N) of length N. Find the maximum non-negative integer x that satisfies the following:

In A, elements greater than or equal to x appear at least x times (including duplicates).

Constraints

1 \leq N \leq 100
0 \leq A_i \leq 10^9
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Output the answer.

Sample Input 1

3
1 2 1

Sample Output 1

In A=(1,2,1):

Elements greater than or equal to 0 appear 3 times.
Elements greater than or equal to 1 appear 3 times.
Elements greater than or equal to 2 appear 1 time.
Elements greater than or equal to 3 appear 0 times.

The maximum non-negative integer that satisfies the condition is 1.

Sample Input 2

7
1 6 2 10 2 3 2

Sample Output 2

E - Festival

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)

i=1,2,\dots,N に対して、以下の問題を解いてください。

i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。

制約

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
入力は全て整数

入力

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

N M
A_1 A_2 \dots A_M

出力

N 行出力せよ。

i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。

入力例 1

3 2
2 3

出力例 1

1
0
0

AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。

1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。

入力例 2

8 5
1 3 4 7 8

出力例 2

Score : 250 points

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
All input values are integers.

Input

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

N M
A_1 A_2 \dots A_M

Output

Print N lines.

The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

F - Centers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

1\leq N \leq 10^5
1 \leq A_j \leq N
i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2

A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

入力例 3

4
2 3 4 3 4 1 3 1 1 4 2 2

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

1\leq N \leq 10^5
1 \leq A_j \leq N
i occurs in A exactly three times, for each i=1,2,\dots,N.
All input values are integers.

Input

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

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

Sample Input 3

4
2 3 4 3 4 1 3 1 1 4 2 2

Sample Output 3

3 4 1 2

G - Pair of Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

2N 個のボールがあります。各ボールには 1 以上 N 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど 2 個ずつ存在します。

これらのボールが、底が地面と平行になるように置かれた M 本の筒に入れられています。はじめ、i \ (1 \leq i \leq M) 本目の筒には k_i 個のボールが入っており、上から j \ (1 \leq j \leq k_i) 番目のボールの色は a_{i, j} です。

あなたの目標は、以下の操作を繰り返すことで M 本の筒全てを空にすることです。

異なる 2 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた 2 つのボールは同じ色で塗られている必要がある。

目標が達成可能かを判定してください。

制約

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 2 \times 10^5
1 \leq k_i\ (1 \leq i \leq M)
1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
\sum_{i=1}^{M} k_i = 2N
全ての x\ (1 \leq x \leq N) について、1 \leq i \leq M かつ 1 \leq j \leq k_i かつ a_{i,j}=x なる整数の組 (i,j) はちょうど 2 つ存在する
入力は全て整数

入力

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

N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}

出力

目標が達成可能なら Yes を、達成不可能なら No を出力せよ。

入力例 1

出力例 1

Yes

以下のように操作を行えばよいです。

1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。
1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。

入力例 2

出力例 2

No

そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。

Score : 400 points

Problem Statement

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 2 \times 10^5
1 \leq k_i\ (1 \leq i \leq M)
1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
\sum_{i=1}^{M} k_i = 2N
For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}

Output

If the objective is achievable, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The objective can be achieved as follows.

Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.