AtCoder Daily Training HARD 2024/04/25 18:30start

Please sign in first.

E - Adjacent Swaps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のボールが左右一列に並んでいます。初め、左から i \, (1 \leq i \leq N) 番目のボールには整数 i が書かれています。

高橋君は Q 回の操作を行いました。 i \, (1 \leq i \leq Q) 回目に行われた操作は次のようなものです。

整数 x_i が書かれているボールをその右隣のボールと入れ替える。ただし、整数 x_i が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。

操作後において左から i \, (1 \leq i \leq N) 番目のボールに書かれている整数を a_i とします。 a_1,\ldots,a_N を求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq x_i \leq N
入力は全て整数

入力

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

N Q
x_1
\vdots
x_Q

出力

a_1,\ldots,a_N を空白区切りで出力せよ。

入力例 1

出力例 1

1 2 3 5 4

操作は以下のように行われます。

1 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 2,1,3,4,5 となる。
2 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
3 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,4,3,5 となる。
4 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
5 と書かれたボールは右端にあるので左隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,5,4 となる。

入力例 2

出力例 2

1 2 3 4 5 7 6

入力例 3

出力例 3

1 2 3 4 5 7 6 8 10 9

Score : 300 points

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq x_i \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
x_1
\vdots
x_Q

Output

Print a_1,\ldots,a_N, with spaces in between.

Sample Input 1

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

Sample Output 3

1 2 3 4 5 7 6 8 10 9

F - Path Graph?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

パスグラフとは

頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
整数 i, j が 1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
入力される値は全て整数
入力で与えられるグラフは単純

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00

入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01

入力例 3

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph?

A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:

For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
All values in the input are integers.
The graph given in the input is simple.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print Yes if the given graph is a path graph; print No otherwise.

Sample Input 1

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01

Sample Input 3

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02

G - ±1 Operation 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。この A に以下を施すことを「操作」と呼びます。

まず、 1 \le i \le N を満たす整数 i を選択する。
次に、以下の 2 つのうちどちらかを選択し、実行する。
- A_i に 1 を加算する。
- A_i から 1 を減算する。

Q 個の質問に答えてください。
i 個目の質問は以下です。

「操作」を 0 回以上何度でも使って A の要素を全て X_i にする時、必要な「操作」の最小回数を求めてください。

制約

入力は全て整数
1 \le N,Q \le 2 \times 10^5
0 \le A_i \le 10^9
0 \le X_i \le 10^9

入力

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

N Q
A_1 A_2 \dots A_N
X_1
X_2
\vdots
X_Q

出力

Q 行にわたって出力せよ。
出力のうち i 行目には、 i 個目の質問に対する答えを整数として出力せよ。

入力例 1

出力例 1

10
71
29

A=(6,11,2,5,5) であり、この入力には 3 つの質問が含まれます。

1 つ目の質問について、 A に以下のように 10 回の「操作」を施すことで、 A の要素を全て 5 にすることができます。

A_1 から 1 減算する。
A_2 から 1 減算することを 6 度繰り返す。
A_3 に 1 加算することを 3 度繰り返す。

9 回以下の「操作」で A の要素を全て 5 にすることはできません。

2 つ目の質問について、 A に 71 回の「操作」を施すことで、 A の要素を全て 20 にすることができます。

3 つ目の質問について、 A に 29 回の「操作」を施すことで、 A の要素を全て 0 にすることができます。

入力例 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

出力例 2

出力が 32bit 整数に収まらない場合もあります。

Score : 400 points

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.

First, choose an integer i such that 1 \le i \le N.
Next, choose and do one of the following.
- Add 1 to A_i.
- Subtract 1 from A_i.

Answer Q questions.
The i-th question is the following.

Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.

Constraints

All values in input are integers.
1 \le N,Q \le 2 \times 10^5
0 \le A_i \le 10^9
0 \le X_i \le 10^9

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
X_1
X_2
\vdots
X_Q

Output

Print Q lines.
The i-th line should contain the answer to the i-th question as an integer.

Sample Input 1

Sample Output 1

10
71
29

We have A=(6,11,2,5,5) and three questions in this input.

For the 1-st question, you can change every element of A to 5 in 10 operations as follows.

Subtract 1 from A_1.
Subtract 1 from A_2 six times.
Add 1 to A_3 three times.

It is impossible to change every element of A to 5 in 9 or fewer operations.

For the 2-nd question, you can change every element of A to 20 in 71 operations.

For the 3-rd question, you can change every element of A to 0 in 29 operations.

Sample Input 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

Sample Output 2

The output may not fit into 32-bit integers.

H - Putting Candies

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の数列 A=(A_0,A_1,\ldots,A_{N-1}) が与えられます。
最初の時点では空の皿があり、高橋君は次の操作を K 回繰り返します。

皿の中のアメの個数を X とする。皿に A_{(X\bmod N)} 個のアメを追加する。ただし、X\bmod N で X を N で割った余りを表す。

K 回の操作の後で、皿の中には何個のアメがあるか求めてください。

制約

2 \leq N \leq 2\times 10^5
1 \leq K \leq 10^{12}
1 \leq A_i\leq 10^6
入力はすべて整数である。

入力

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

N K
A_0 A_1 \ldots A_{N-1}

出力

答えを出力せよ。

入力例 1

5 3
2 1 6 3 1

出力例 1

皿の中のアメの個数は次のように変化します。

1 回目の操作において、X=0 であるので、アメは A_{(0\mod 5)}=A_0=2 個追加されます。
2 回目の操作において、X=2 であるので、アメは A_{(2\mod 5)}=A_2=6 個追加されます。
3 回目の操作において、X=8 であるので、アメは A_{(8\mod 5)}=A_3=3 個追加されます。

よって、3 回の操作の後で、皿には 11 個のアメがあります。出力する値は N で割った余りではない事に注意してください。

入力例 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

出力例 2

826617499998784056

答えは 32 bit 整数型に収まらない場合があります。

Score : 500 points

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

2 \leq N \leq 2\times 10^5
1 \leq K \leq 10^{12}
1 \leq A_i\leq 10^6
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 \ldots A_{N-1}

Output

Print the answer.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

The number of candies on the dish transitions as follows.

In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

I - Usual Color Ball Problems

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

正整数 N, M, K と、長さ N の正整数列 (C_1, C_2, \ldots, C_N) が与えられるので、 r = 0, 1, 2, \ldots, N-1 の場合それぞれについて、下記の問題の答えを出力してください。

色がついた N 個のボールからなる列があり、i = 1, 2, \ldots, N について、列の先頭から i 番目にあるボールの色は C_i です。また、1 から M の番号がつけられた M 個の空の箱があります。

下記の手順を行った後に箱に入っているボールの総数を求めてください。

まず、下記の操作を r 回行う。

列の先頭のボール 1 個を列の最後尾に移動する。

その後、列にボールが 1 個以上残っている限り、下記の操作を繰り返す。

列の先頭のボールと同じ色のボールが既に 1 個以上 K 個未満入っている箱が存在する場合、その箱に列の先頭のボールを入れる。

そのような箱が存在しない場合、

空の箱が存在するなら、そのうち番号が最小のものに、列の先頭のボールを入れる。

空の箱が存在しない場合、列の先頭のボールをどの箱にも入れず、食べる。

制約

入力される値はすべて整数
1 \leq N \leq 2 \times 10^5
1 \leq M, K \leq N
1 \leq C_i \leq N

入力

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

N M K
C_1 C_2 \ldots C_N

出力

r = 0, 1, 2, \ldots, N-1 のそれぞれの場合の問題の答え X_r を下記の通りに N 行にわたって出力せよ。

X_0
X_1
\vdots
X_{N-1}

入力例 1

7 2 2
1 2 3 5 2 5 4

出力例 1

例として、r = 1 の場合の手順を説明します。まず「列の先頭のボール 1 個を列の最後尾に移動する」ことを 1 回行い、ボールの色の列は (2, 3, 5, 2, 5, 4, 1) となります。その後、ボールを箱に入れていく操作を下記の通りに行います。

1 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 1 に入れます。
2 回目の操作：先頭のボールの色は 3 です。色 3 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 2 に入れます。
3 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
4 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱として箱 1 が存在するため、先頭のボールを箱 1 に入れます。
5 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
6 回目の操作：先頭のボールの色は 4 です。色 4 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
7 回目の操作：先頭のボールの色は 1 です。色 1 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。

最終的に箱に入っているボールの総数は 3 個であるので、r = 1 の問題の答えは 3 です。

入力例 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

出力例 2

Score: 550 points

Problem Statement

You are given positive integers N, M, K, and a sequence of positive integers of length N, (C_1, C_2, \ldots, C_N). For each r = 0, 1, 2, \ldots, N-1, print the answer to the following problem.

There is a sequence of N colored balls. For i = 1, 2, \ldots, N, the color of the i-th ball from the beginning of the sequence is C_i. Additionally, there are M empty boxes numbered 1 to M.

Determine the total number of balls in the boxes after performing the following steps.

First, perform the following operation r times.

Move the frontmost ball in the sequence to the end of the sequence.

Then, repeat the following operation as long as at least one ball remains in the sequence.

If there is a box that already contains at least one but fewer than K balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.

If there is no such box,

If there is an empty box, put the frontmost ball into the one with the smallest box number.

If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

All input values are integers.
1 \leq N \leq 2 \times 10^5
1 \leq M, K \leq N
1 \leq C_i \leq N

Input

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

N M K
C_1 C_2 \ldots C_N

Output

Print the answer X_r to the problem for each r = 0, 1, 2, \ldots, N-1 over N lines as follows:

X_0
X_1
\vdots
X_{N-1}

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

For example, let us explain the procedure for r = 1. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes (2, 3, 5, 2, 5, 4, 1). Then, proceed with the operation of putting balls into boxes as follows:

First operation: The color of the frontmost ball is 2. There is no box with at least one but fewer than two balls of color 2, so put the frontmost ball into the empty box with the smallest box number, box 1.
Second operation: The color of the frontmost ball is 3. There is no box with at least one but fewer than two balls of color 3, so put the frontmost ball into the empty box with the smallest box number, box 2.
Third operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
Fourth operation: The color of the frontmost ball is 2. There is a box, box 1, with at least one but fewer than two balls of color 2, so put the frontmost ball into box 1.
Fifth operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
Sixth operation: The color of the frontmost ball is 4. There is no box with at least one but fewer than two balls of color 4 and no empty boxes, so eat the frontmost ball.
Seventh operation: The color of the frontmost ball is 1. There is no box with at least one but fewer than two balls of color 1 and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is 3, so the answer to the problem for r = 1 is 3.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2