AtCoder Grand Contest 035

A - XOR Circle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

すぬけ君は N 枚の帽子を持っています。i 枚目の帽子には整数 a_i が書かれています。

N 頭のラクダが円環状に並んでいます。すぬけ君はそれぞれのラクダに 1 枚の帽子を被せようとしています。

どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば Yes を、そうでなければ No を出力してください。

両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の被っている帽子に書かれた数と等しい

ビットごとの排他的論理和について

n 個の非負整数 x_1,x_2, \ldots, x_n の排他的論理和 x_1 \oplus x_2 \oplus \ldots \oplus x_n は以下のように定義されます。

x_1 \oplus x_2 \oplus \ldots \oplus x_n を二進表記した際の 2^k(k \geq 0) の位の数は x_1,x_2, \ldots, x_n のうち、二進表記した際の 2^k(k \geq 0) の位の数が 1 となるものの個数が奇数ならば 1、そうでなければ 0 となる。

例えば、3 \oplus 5 = 6 となります。

制約

入力は全て整数
3 \leq N \leq 10^{5}
0 \leq a_i \leq 10^{9}

入力

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

N
a_1 a_2 \ldots a_{N}

出力

答えを出力せよ。

入力例 1

3
1 2 3

出力例 1

Yes

1,2,3 が書かれた帽子を時計回りに被せたとき、どのラクダも問題文中の条件を満たすため、答えは Yes となります。

入力例 2

4
1 2 4 8

出力例 2

No

そのような被せ方は存在しません。よって、答えは No となります。

Score : 300 points

Problem Statement

Snuke has N hats. The i-th hat has an integer a_i written on it.

There are N camels standing in a circle. Snuke will put one of his hats on each of these camels.

If there exists a way to distribute the hats to the camels such that the following condition is satisfied for every camel, print Yes; otherwise, print No.

The bitwise XOR of the numbers written on the hats on both adjacent camels is equal to the number on the hat on itself.

What is XOR?

The bitwise XOR x_1 \oplus x_2 \oplus \ldots \oplus x_n of n non-negative integers x_1, x_2, \ldots, x_n is defined as follows: - When x_1 \oplus x_2 \oplus \ldots \oplus x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even. For example, 3 \oplus 5 = 6.

Constraints

All values in input are integers.
3 \leq N \leq 10^{5}
0 \leq a_i \leq 10^{9}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_{N}

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

Yes

If we put the hats with 1, 2, and 3 in this order, clockwise, the condition will be satisfied for every camel, so the answer is Yes.

Sample Input 2

4
1 2 4 8

Sample Output 2

No

There is no such way to distribute the hats; the answer is No.

B - Even Degrees

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。頂点には 1 から N までの番号がついており、i 本目の辺は頂点 A_i と頂点 B_i を結んでいます。高橋君は、与えられたグラフのすべての辺にどちらかの向きをつけて有向グラフを作ります。どの頂点から出る辺の本数も偶数になるような有向グラフを作ることが可能かどうか判定し、可能ならそのような例をひとつ構成してください。

ノート

無向グラフが単純であるとは、自己ループと多重辺を含まないことを指します。

制約

2 \leq N \leq 10^5
N-1 \leq M \leq 10^5
1 \leq A_i,B_i \leq N (1\leq i\leq M)
与えられるグラフは単純かつ連結

入力

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

N M
A_1 B_1
:
A_M B_M

出力

条件を満たす向き付けが不可能な場合、-1 を出力せよ。そうでない場合、以下の形式でグラフのすべての辺の向きを重複なく出力せよ。

C_1 D_1
:
C_M D_M

ただし、組 (C_i,D_i) は C_i から頂点 D_i に向かって向き付けられた辺が存在することを表す。辺は任意の順で出力して構わない。

入力例 1

出力例 1

このように向き付けることで、頂点 1,3 からは 2 本、頂点 2,4 からは 0 本の辺が出るようになります。

入力例 2

出力例 2

-1

Score : 700 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex A_i and Vertex B_i. Takahashi will assign one of the two possible directions to each of the edges in the graph to make a directed graph. Determine if it is possible to make a directed graph with an even number of edges going out from every vertex. If the answer is yes, construct one such graph.

Notes

An undirected graph is said to be simple when it contains no self-loops or multiple edges.

Constraints

2 \leq N \leq 10^5
N-1 \leq M \leq 10^5
1 \leq A_i,B_i \leq N (1\leq i\leq M)
The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If it is impossible to assign directions to satisfy the requirement, print -1. Otherwise, print an assignment of directions that satisfies the requirement, in the following format:

C_1 D_1
:
C_M D_M

Here each pair (C_i, D_i) means that there is an edge directed from Vertex C_i to Vertex D_i. The edges may be printed in any order.

Sample Input 1

Sample Output 1

After this assignment of directions, Vertex 1 and 3 will each have two outgoing edges, and Vertex 2 and 4 will each have zero outgoing edges.

Sample Input 2

Sample Output 2

-1

C - Skolem XOR Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

整数 N が与えられます。1 から 2N までの番号がついた 2N 個の頂点を持つ木であって次の条件を満たすものが存在するか判定し、存在するならばその一例を示してください。

1 以上 N 以下の各整数 i について、頂点 i, N+i の重みが i であるとする。このとき、1 以上 N 以下の各整数 i について、頂点 i, N+i 間のパス上にある頂点 (両端を含む) の重みのビットごとの排他的論理和が i である。

制約

入力は全て整数
1 \leq N \leq 10^{5}

入力

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

出力

問題文中の条件を満たす木が存在するならば Yes を、そうでなければ No を出力せよ。その後、存在するならば続く 2N-1 行にそのような木の 2N-1 本の辺を以下の形式で出力せよ。

a_{1} b_{1}
\vdots
a_{2N-1} b_{2N-1}

ここで、各組 (a_i, b_i) は木に頂点 a_i, b_i を結ぶ辺が存在することを表す。辺は任意の順で出力して構わない。

入力例 1

出力例 1

出力例は以下のグラフを表します。

入力例 2

出力例 2

No

条件を満たす木が存在しません。

Score : 700 points

Problem Statement

You are given an integer N. Determine if there exists a tree with 2N vertices numbered 1 to 2N satisfying the following condition, and show one such tree if the answer is yes.

Assume that, for each integer i between 1 and N (inclusive), Vertex i and N+i have the weight i. Then, for each integer i between 1 and N, the bitwise XOR of the weights of the vertices on the path between Vertex i and N+i (including themselves) is i.

Constraints

N is an integer.
1 \leq N \leq 10^{5}

Input

Input is given from Standard Input in the following format:

Output

If there exists a tree satisfying the condition in the statement, print Yes; otherwise, print No. Then, if such a tree exists, print the 2N-1 edges of such a tree in the subsequent 2N-1 lines, in the following format:

a_{1} b_{1}
\vdots
a_{2N-1} b_{2N-1}

Here each pair (a_i, b_i) means that there is an edge connecting Vertex a_i and b_i. The edges may be printed in any order.

Sample Input 1

Sample Output 1

The sample output represents the following graph:

Sample Input 2

Sample Output 2

No

There is no tree satisfying the condition.

D - Add and Remove

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

非負整数のひとつ書かれたカードが N 枚積まれた山があります。上から i 番目のカードに書かれた整数は A_i です。

すぬけ君は、以下の操作をカードが 2 枚になるまで繰り返します。

連続して積まれている 3 枚のカードを選ぶ。
3 枚のうち真ん中のカードを食べる。
あとの 2 枚のカードに書かれている整数を、その整数に食べたカードに書かれていた整数を足してできる整数に書き換える。
食べなかった 2 枚のカードを、順序を保ったまま山のもとの位置に戻す。

最終的に残る 2 枚のカードに書かれた整数の和の最小値を求めてください。

制約

2 \leq N \leq 18
0 \leq A_i \leq 10^9 (1\leq i\leq N)
入力はすべて整数である

入力

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

N
A_1 A_2 ... A_N

出力

最終的に残る 2 枚のカードに書かれた整数の和の最小値を出力せよ。

入力例 1

4
3 1 4 2

出力例 1

以下の操作を行うことで、最終的に残る 2 枚のカードに書かれた整数の和を最小にできます。

最初、カードに書かれた整数は順に 3,1,4,2 である。
1,2,3 番目のカードを選ぶ。1 の書かれた 2 枚目のカードを食べ、残ったカードに書かれた整数に 1 を足し、山のもとの位置に戻す。カードに書かれた整数は順に 4,5,2 となる。
1,2,3 番目のカードを選ぶ。5 の書かれた 2 枚目のカードを食べ、残ったカードに書かれた整数に 5 を足し、山のもとの位置に戻す。カードに書かれた整数は順に 9,7 となる。
最後に残った 2 枚のカードに書かれた整数の和は 16 になる。

入力例 2

6
5 2 4 1 6 9

出力例 2

入力例 3

10
3 1 4 1 5 9 2 6 5 3

出力例 3

Score : 1000 points

Problem Statement

There is a stack of N cards, each of which has a non-negative integer written on it. The integer written on the i-th card from the top is A_i.

Snuke will repeat the following operation until two cards remain:

Choose three consecutive cards from the stack.
Eat the middle card of the three.
For each of the other two cards, replace the integer written on it by the sum of that integer and the integer written on the card eaten.
Return the two cards to the original position in the stack, without swapping them.

Find the minimum possible sum of the integers written on the last two cards remaining.

Constraints

2 \leq N \leq 18
0 \leq A_i \leq 10^9 (1\leq i\leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sum of the integers written on the last two cards remaining.

Sample Input 1

4
3 1 4 2

Sample Output 1

We can minimize the sum of the integers written on the last two cards remaining by doing as follows:

Initially, the integers written on the cards are 3, 1, 4, and 2 from top to bottom.
Choose the first, second, and third card from the top. Eat the second card with 1 written on it, add 1 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 4, 5, and 2 from top to bottom.
Choose the first, second, and third card from the top. Eat the second card with 5 written on it, add 5 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 9 and 7 from top to bottom.
The sum of the integers written on the last two cards remaining is 16.

Sample Input 2

6
5 2 4 1 6 9

Sample Output 2

Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

E - Develop

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

黒板に -10^{18} から 10^{18} までの整数が 1 個ずつ書かれています。高橋君は、以下の一連の操作を 0 回以上好きなだけ繰り返します。

黒板に書かれている整数のうち 1 以上 N 以下のものをひとつ選ぶ。選んだ整数を x とし、x を黒板から消す。
黒板に x-2 が書かれていないなら、x-2 を書き加える。
黒板に x+K が書かれていないなら、x+K を書き加える。

何回かの操作後、黒板に書かれている数の集合としてありうるものの個数を M で割った余りを求めてください。ただし、2 つの集合が異なるとは、その片方だけに現れるような整数が存在することを指します。

制約

1 \leq K\leq N \leq 150
10^8\leq M\leq 10^9
N,K,M は整数である

入力

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

N K M

出力

何回かの操作後、黒板に書かれている数の集合としてありうるものの個数を M で割った余りを出力せよ。

入力例 1

3 1 998244353

出力例 1

0 以下または 4 以上の整数すべてと、1,2,3 のうちの 1 つ以上を含むような集合すべてが条件を満たし、これは 7 通りあります。

入力例 2

6 3 998244353

出力例 2

入力例 3

9 4 702443618

出力例 3

入力例 4

17 7 208992811

出力例 4

入力例 5

123 45 678901234

出力例 5

256109226

Score : 1600 points

Problem Statement

There is a blackboard on which all integers from -10^{18} through 10^{18} are written, each of them appearing once. Takahashi will repeat the following sequence of operations any number of times he likes, possibly zero:

Choose an integer between 1 and N (inclusive) that is written on the blackboard. Let x be the chosen integer, and erase x.
If x-2 is not written on the blackboard, write x-2 on the blackboard.
If x+K is not written on the blackboard, write x+K on the blackboard.

Find the number of possible sets of integers written on the blackboard after some number of operations, modulo M. We consider two sets different when there exists an integer contained in only one of the sets.

Constraints

1 \leq K\leq N \leq 150
10^8\leq M\leq 10^9
N, K, and M are integers.

Input

Input is given from Standard Input in the following format:

N K M

Output

Print the number of possible sets of integers written on the blackboard after some number of operations, modulo M.

Sample Input 1

3 1 998244353

Sample Output 1

Every set containing all integers less than 1, all integers greater than 3, and at least one of the three integers 1, 2, and 3 satisfies the condition. There are seven such sets.

Sample Input 2

6 3 998244353

Sample Output 2

Sample Input 3

9 4 702443618

Sample Output 3

Sample Input 4

17 7 208992811

Sample Output 4

Sample Input 5

123 45 678901234

Sample Output 5

256109226

F - Two Histograms

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

N 行 M 列のマス目があります。高橋君は、以下のようにして各マスに整数を書き込みます。

まず、すべてのマスに 0 を書き込む
i=1,2,...,N に対し、整数 k_i (0\leq k_i\leq M) を選び、上から i 行目の左から k_i 個のマスに書かれた整数すべてに 1 を足す
j=1,2,...,M に対し、整数 l_j (0\leq l_j\leq N) を選び、左から j 列目の上から l_j 個のマスに書かれた整数すべてに 1 を足す

こうして、各マスに 0,1,2 のいずれかの整数の書かれたマス目が出来上がります。最終的にできる可能性のある相異なるマス目の個数を 998244353 で割った余りを求めてください。ただし、2 つのマス目が異なるとは、あるマスが存在してそのマスに書かれた整数が異なることを指します。

制約

1 \leq N,M \leq 5\times 10^5
N,M は整数である

入力

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

N M

出力

最終的にできる可能性のある相異なるマス目の個数を 998244353 で割った余りを出力せよ。

入力例 1

1 2

出力例 1

左のマスに a が、右のマスに b が書き込まれたマス目を (a,b) と表すことにすると、(0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) の 8 通りのマス目ができる可能性があります。

入力例 2

2 3

出力例 2

入力例 3

10 7

出力例 3

995651918

入力例 4

314159 265358

出力例 4

70273732

Score : 1800 points

Problem Statement

We have a square grid with N rows and M columns. Takahashi will write an integer in each of the squares, as follows:

First, write 0 in every square.
For each i=1,2,...,N, choose an integer k_i (0\leq k_i\leq M), and add 1 to each of the leftmost k_i squares in the i-th row.
For each j=1,2,...,M, choose an integer l_j (0\leq l_j\leq N), and add 1 to each of the topmost l_j squares in the j-th column.

Now we have a grid where each square contains 0, 1, or 2. Find the number of different grids that can be made this way, modulo 998244353. We consider two grids different when there exists a square with different integers.

Constraints

1 \leq N,M \leq 5\times 10^5
N and M are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of different grids that can be made, modulo 998244353.

Sample Input 1

1 2

Sample Output 1

Let (a,b) denote the grid where the square to the left contains a and the square to the right contains b. Eight grids can be made: (0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1), and (2,2).

Sample Input 2

2 3

Sample Output 2

Sample Input 3

10 7

Sample Output 3

995651918

Sample Input 4

314159 265358

Sample Output 4

70273732