AtCoder Regular Contest 225

A - Four Coloring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N \times N のグリッド X があります。上から i 行目、左から j 列目のマスを (i,j) で表します。辺を共有する 2 マスを 隣接する と呼ぶことにします。

マス (i,j) は色 X_{i,j} で塗られています。色は 1,2,3,4 のいずれかであり、隣接するマスは異なる色で塗られています。

あなたは N \times N のグリッド Y を用意し、各マスに色を塗ります。Y のマス (i,j) に塗る色を Y_{i,j} と表します。

以下の条件を満たすような色の塗り方を 1 つ求めてください。

Y の各マスの色は 1,2,3,4 のいずれかである。 隣接するマスの色は同じでも良い。
隣接する任意の 2 マス (i_1,j_1), (i_2,j_2) について、以下が成り立つ。

|X_{i_1,j_1} - X_{i_2,j_2}|=1 ならば |Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2
|X_{i_1,j_1} - X_{i_2,j_2}|\ge2 ならば |Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1

なお、条件を満たすような色の塗り方は必ず存在することが証明できます。

制約

2 \le N \le 500
1 \le X_{i,j} \le 4
X の隣接するマスは異なる色で塗られている。
入力される値は全て整数

入力

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

N
X_{1,1} X_{1,2} \ldots X_{1,N}
X_{2,1} X_{2,2} \ldots X_{2,N}
\vdots
X_{N,1} X_{N,2} \ldots X_{N,N}

出力

条件を満たす Y を以下の形式で出力せよ。

Y_{1,1} Y_{1,2} \ldots Y_{1,N}
Y_{2,1} Y_{2,2} \ldots Y_{2,N}
\vdots
Y_{N,1} Y_{N,2} \ldots Y_{N,N}

入力例 1

出力例 1

4 1 4
1 3 2
4 4 2

入力された X、出力した Y それぞれについて、例えば隣接する 2 マス (1,1), (1,2) を見ると、以下のようになります。

|X_{1,1} - X_{1,2}| = |1 - 2| = 1
|Y_{1,1} - Y_{1,2}| = |4 - 1| = 3

また、隣接する 2 マス (2,2), (3,2) を見ると、以下のようになります。

|X_{2,2} - X_{3,2}| = |1 - 3| = 2
|Y_{2,2} - Y_{3,2}| = |3 - 4| = 1

このように、Y は隣接する任意の 2 マスに対して条件を満たすことが確かめられるため、正解となります。

入力例 2

2
1 4
4 1

出力例 2

1 1
1 1

Y の隣接するマスの色は同じでも構いません。

Score : 500 points

Problem Statement

There is an N \times N grid X. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. We call two cells that share an edge adjacent.

Cell (i,j) is painted with color X_{i,j}. The color is one of 1,2,3,4, and adjacent cells are painted with different colors.

You will prepare an N \times N grid Y and paint each cell. Let Y_{i,j} denote the color painted on cell (i,j) of Y.

Find one way of painting that satisfies the following conditions.

The color of each cell of Y is one of 1,2,3,4. Adjacent cells may have the same color.
For any two adjacent cells (i_1,j_1) and (i_2,j_2), the following holds.

If |X_{i_1,j_1} - X_{i_2,j_2}|=1, then |Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2.
If |X_{i_1,j_1} - X_{i_2,j_2}|\ge2, then |Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1.

It can be proved that a way of painting satisfying the conditions always exists.

Constraints

2 \le N \le 500
1 \le X_{i,j} \le 4
Adjacent cells of X are painted with different colors.
All input values are integers.

Input

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

N
X_{1,1} X_{1,2} \ldots X_{1,N}
X_{2,1} X_{2,2} \ldots X_{2,N}
\vdots
X_{N,1} X_{N,2} \ldots X_{N,N}

Output

Output a Y satisfying the conditions in the following format:

Y_{1,1} Y_{1,2} \ldots Y_{1,N}
Y_{2,1} Y_{2,2} \ldots Y_{2,N}
\vdots
Y_{N,1} Y_{N,2} \ldots Y_{N,N}

Sample Input 1

Sample Output 1

4 1 4
1 3 2
4 4 2

For the input X and the output Y, for example, looking at the two adjacent cells (1,1) and (1,2), we have the following.

|X_{1,1} - X_{1,2}| = |1 - 2| = 1
|Y_{1,1} - Y_{1,2}| = |4 - 1| = 3

Also, looking at the two adjacent cells (2,2) and (3,2), we have the following.

|X_{2,2} - X_{3,2}| = |1 - 3| = 2
|Y_{2,2} - Y_{3,2}| = |3 - 4| = 1

In this way, it can be confirmed that Y satisfies the conditions for any two adjacent cells, so this is a correct answer.

Sample Input 2

2
1 4
4 1

Sample Output 2

1 1
1 1

Adjacent cells of Y may have the same color.

B - Independent Nim

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

長さ N の整数列 A があります。A の各要素は 0 または 1 です。

Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行います。

A の要素から 1 であるものを 1 つ以上選び、それらを 0 にする。ただし、隣接する要素を同時に選ぶことはできない。

先に操作を行えなくなったプレイヤーの負けです。

両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \le T \le 10^5
1 \le N \le 2\times 10^5
A_i = 0 または A_i = 1
全てのテストケースにおける N の総和は 2\times 10^5 以下
入力される値は全て整数

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各ケースは以下の形式で与えられる。

N
A_1 A_2 \cdots A_N

出力

T 行出力せよ。i 行目には \text{case}_i について、Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。

入力例 1

3
5
1 0 1 0 1
2
1 1
14
1 1 1 0 1 1 1 1 0 1 1 1 1 1

出力例 1

Alice
Bob
Alice

1 つ目のテストケースについて、Alice が最初の操作で 1,3,5 番目の要素を選んで 0 にすることで、全ての要素を 0 にすることができます。

次に Bob は操作を行えないため、両者が最善を尽くしたとき Alice が勝利します。

2 つ目のテストケースについて、Alice は最初の操作でどちらか一方の要素しか選ぶことはできません。

Score : 600 points

Problem Statement

There is an integer sequence A of length N. Each element of A is 0 or 1.

Alice and Bob play a game. Starting with Alice, they alternately perform the following operation.

Choose one or more elements of A that are 1, and set them to 0. Here, it is forbidden to choose adjacent elements simultaneously.

The player who is first unable to perform the operation loses.

Determine which player wins when both players play optimally.

You are given T test cases; solve each of them.

Constraints

1 \le T \le 10^5
1 \le N \le 2\times 10^5
A_i = 0 or A_i = 1.
The sum of N over all test cases is at most 2\times 10^5.
All input values are integers.

Input

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

Output T lines. The i-th line should contain Alice if Alice wins for \text{case}_i, and Bob if Bob wins.

Sample Input 1

3
5
1 0 1 0 1
2
1 1
14
1 1 1 0 1 1 1 1 0 1 1 1 1 1

Sample Output 1

Alice
Bob
Alice

For the first test case, Alice can set all elements to 0 by choosing the first, third, and fifth elements and setting them to 0 in her first operation.

Then, Bob cannot perform an operation, so Alice wins when both players play optimally.

For the second test case, Alice can only choose one of the two elements in her first operation.

C - K Spanning Tree

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

N 頂点 M 辺の単純連結無向グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結ぶ重み c_i の辺です。ここで、各辺の重みは 0 または 1 です。

非負整数 K が与えられます。G の全域木であって、その全域木を構成する辺の重みの和がちょうど K であるものが存在するかを判定し、存在するなら一つ求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \le T \le 10^5
2 \le N \le 2\times 10^5
N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)
0 \le K \le N-1
1 \le a_i,b_i \le N
c_i=0 または c_i=1
グラフ G は単純連結である。
全てのテストケースにおける N の総和は 2\times 10^5 以下
全てのテストケースにおける M の総和は 2\times 10^5 以下
入力される値は全て整数

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各ケースは以下の形式で与えられる。

N M K
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_M b_M c_M

出力

T 行出力せよ。i 行目には \text{case}_i に対する答えを出力せよ。

条件を満たす全域木が存在しない場合は -1 を出力せよ。

そうでない場合、そのケースの全域木を構成する辺の番号を x_1,x_2,\cdots,x_{N-1} として、以下の形式で出力せよ。

x_1 x_2 \cdots x_{N-1}

x_1,x_2,\cdots,x_{N-1} の並び順は自由である。辺番号は各ケース内での入力順に対応する。解が複数存在する場合は、どれを出力しても正解とみなされる。

入力例 1

出力例 1

1 4 5
-1

1 つ目のケースについて、辺 1,4,5 から構成されるグラフは G の全域木となっており、また辺の重みの和が 2 であるため、条件を満たします。

2 4 5、 4 1 5 などの出力も正解となります。

2 つ目のケースについて、グラフ G の全域木の辺の重みの和を 1 にすることはできません。

Score : 600 points

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges. Edge i connects vertices a_i and b_i, and has weight c_i. Here, each edge's weight is 0 or 1.

You are given a non-negative integer K. Determine whether there exists a spanning tree of G such that the sum of the weights of the edges composing the spanning tree is exactly K, and if one exists, find one.

You are given T test cases; solve each of them.

Constraints

1 \le T \le 10^5
2 \le N \le 2\times 10^5
N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)
0 \le K \le N-1
1 \le a_i,b_i \le N
c_i=0 or c_i=1.
The graph G is simple and connected.
The sum of N over all test cases is at most 2\times 10^5.
The sum of M over all test cases is at most 2\times 10^5.
All input values are integers.

Input

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each case is given in the following format:

N M K
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_M b_M c_M

Output

Output T lines. The i-th line should contain the answer for \text{case}_i.

If there is no spanning tree satisfying the condition, output -1.

Otherwise, let x_1,x_2,\cdots,x_{N-1} be the numbers of the edges composing a spanning tree for that case, and output them in the following format:

x_1 x_2 \cdots x_{N-1}

x_1,x_2,\cdots,x_{N-1} can be in any order. The edge numbers correspond to the input order within each case. If multiple solutions exist, any of them is accepted.

Sample Input 1

Sample Output 1

1 4 5
-1

For the first case, the graph composed of edges 1,4,5 is a spanning tree of G, and the sum of its edge weights is 2, so it satisfies the condition.

Outputs such as 2 4 5 and 4 1 5 are also accepted.

For the second case, the sum of the edge weights of a spanning tree of graph G cannot be 1.

D - Gap Swap (easy)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

この問題は E 問題と設定が似ていますが、操作にかかるコストが異なります。

(1,2,\ldots,N) の順列 P があります。P に対して以下の操作を行えます。

1 \le i < j \le N を満たす整数 i,j を選ぶ。ただし、i < k < j を満たす全ての整数 k について P_k=k でなければならない。その後、P_i,P_j を入れ替える。
この操作には コストが \boldsymbol{j-i} かかる。

なお、i+1=j の場合、i<k<j を満たす整数 k は存在しないため、操作は常に行えます。したがって、P を昇順にするような操作手順は必ず存在します。

P を昇順にするために必要なコストの和の最小値を求めてください。

制約

2 \le N \le 5\times 10^5
1 \le P_i \le N
P は (1,2,\ldots,N) の順列
入力される値は全て整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

6
6 2 3 5 4 1

出力例 1

例えば以下のような手順で 2 回操作をすることでコストの和 6 で P を昇順に並べ替えることができます。

1 回目の操作 : i=4, j=5 を選び、P_4, P_5 を入れ替える。コストが 1 かかる。
2 回目の操作 : i=1, j=6 を選び、P_1, P_6 を入れ替える。コストが 5 かかる。

6 より小さいコストで昇順にすることはできないため、答えは 6 です。

入力例 2

3
1 2 3

出力例 2

必要なコストの和が 0 の場合もあります。

Score : 600 points

Problem Statement

This problem has a similar setting to Problem E, but the cost of the operation is different.

There is a permutation P of (1,2,\ldots,N). You can perform the following operation on P.

Choose integers i and j satisfying 1 \le i < j \le N. Here, P_k=k must hold for every integer k satisfying i < k < j. Then, swap P_i and P_j.
This operation incurs a cost of \boldsymbol{j-i}.

Note that if i+1=j, there is no integer k satisfying i<k<j, so the operation can always be performed. Therefore, there always exists a sequence of operations that sorts P into ascending order.

Find the minimum total cost required to sort P into ascending order.

Constraints

2 \le N \le 5\times 10^5
1 \le P_i \le N
P is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

6
6 2 3 5 4 1

Sample Output 1

For example, by performing two operations as follows, P can be sorted into ascending order with a total cost of 6.

First operation: choose i=4, j=5, and swap P_4, P_5. This costs 1.
Second operation: choose i=1, j=6, and swap P_1, P_6. This costs 5.

P cannot be sorted into ascending order with a cost less than 6, so the answer is 6.

Sample Input 2

3
1 2 3

Sample Output 2

The required total cost can be 0.

E - Gap Swap (hard)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

この問題は D 問題と設定が似ていますが、操作にかかるコストが異なります。

(1,2,\ldots,N) の順列 P があります。P に対して以下の操作を行えます。

1 \le i < j \le N を満たす整数 i,j を選ぶ。ただし、i < k < j を満たす全ての整数 k について P_k=k でなければならない。その後、P_i,P_j を入れ替える。
この操作には コストが \boldsymbol{1} かかる。

P を昇順にするために必要なコストの和の最小値を求めてください。

制約

2 \le N \le 5\times 10^5
1 \le P_i \le N
P は (1,2,\ldots,N) の順列
入力される値は全て整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

6
6 2 3 5 4 1

出力例 1

例えば以下のような手順で 2 回操作をすることでコストの和 2 で P を昇順に並べ替えることができます。

1 回目の操作 : i=4, j=5 を選び、P_4, P_5 を入れ替える。コストが 1 かかる。
2 回目の操作 : i=1, j=6 を選び、P_1, P_6 を入れ替える。コストが 1 かかる。

2 より小さいコストで昇順にすることはできないため、答えは 2 です。

入力例 2

3
1 2 3

出力例 2

必要なコストの和が 0 の場合もあります。

Score : 900 points

Problem Statement

This problem has a similar setting to Problem D, but the cost of the operation is different.

There is a permutation P of (1,2,\ldots,N). You can perform the following operation on P.

Choose integers i and j satisfying 1 \le i < j \le N. Here, P_k=k must hold for every integer k satisfying i < k < j. Then, swap P_i and P_j.
This operation incurs a cost of \boldsymbol{1}.

Find the minimum total cost required to sort P into ascending order.

Constraints

2 \le N \le 5\times 10^5
1 \le P_i \le N
P is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

6
6 2 3 5 4 1

Sample Output 1

For example, by performing two operations as follows, P can be sorted into ascending order with a total cost of 2.

First operation: choose i=4, j=5, and swap P_4, P_5. This costs 1.
Second operation: choose i=1, j=6, and swap P_1, P_6. This costs 1.

P cannot be sorted into ascending order with a cost less than 2, so the answer is 2.

Sample Input 2

3
1 2 3

Sample Output 2

The required total cost can be 0.