AtCoder Grand Contest 016

A - Shrinking

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

すぬけ君は、次のルールに従い、長さ N の文字列 t を長さ N - 1 の文字列 t' へ変えることができます。

各 i (1 ≤ i ≤ N - 1) について、t' の i 文字目は t の i, i + 1 文字目のどちらかである。

英小文字のみからなる文字列 s があります。すぬけ君の目標は、s に上記の操作を繰り返し行い、s が単一の文字のみからなるようにすることです。目標を達成するために必要な操作回数の最小値を求めてください。

制約

1 ≤ |s| ≤ 100
s は英小文字のみからなる。

入力

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

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

入力例 1

serval

出力例 1

例えば、serval → srvvl → svvv → vvv と変えればよいです。

入力例 2

jackal

出力例 2

例えば、jackal → aacaa → aaaa と変えればよいです。

入力例 3

zzz

出力例 3

最初から s が単一の文字のみからなっています。

入力例 4

whbrjpjyhsrywlqjxdbrbaomnw

出力例 4

8 回の操作によって、s を rrrrrrrrrrrrrrrrrr へ変えることができます。

Score : 300 points

Problem Statement

Snuke can change a string t of length N into a string t' of length N - 1 under the following rule:

For each i (1 ≤ i ≤ N - 1), the i-th character of t' must be either the i-th or (i + 1)-th character of t.

There is a string s consisting of lowercase English letters. Snuke's objective is to apply the above operation to s repeatedly so that all the characters in s are the same. Find the minimum necessary number of operations.

Constraints

1 ≤ |s| ≤ 100
s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

Print the minimum necessary number of operations to achieve the objective.

Sample Input 1

serval

Sample Output 1

One solution is: serval → srvvl → svvv → vvv.

Sample Input 2

jackal

Sample Output 2

One solution is: jackal → aacaa → aaaa.

Sample Input 3

zzz

Sample Output 3

All the characters in s are the same from the beginning.

Sample Input 4

whbrjpjyhsrywlqjxdbrbaomnw

Sample Output 4

In 8 operations, he can change s to rrrrrrrrrrrrrrrrrr.

B - Colorful Hats

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

N 匹の猫がいます。猫には 1 から N まで番号が振られています。

各猫はある色の帽子を被っています。猫 i は「自分を除く N-1 匹の猫が被っている帽子の色の種類数はちょうど a_i である」と言っています。

すべての猫の発言と矛盾しないような帽子の色の組合せが存在するか判定してください。

制約

2 ≤ N ≤ 10^5
1 ≤ a_i ≤ N-1

入力

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

N
a_1 a_2 ... a_N

出力

すべての猫の発言と矛盾しないような帽子の色の組合せが存在するならば、Yes を出力せよ。存在しないならば、No を出力せよ。

入力例 1

3
1 2 2

出力例 1

Yes

例えば、猫 1, 2, 3 の帽子の色がそれぞれ赤、青、青ならば、すべての猫の発言と矛盾しません。

入力例 2

3
1 1 2

出力例 2

No

猫 1 の発言から、猫 2, 3 の帽子の色は同一です。また、猫 2 の発言から、猫 1, 3 の帽子の色は同一です。よって、猫 1, 2 の帽子の色は同一ですが、これは猫 3 の発言に矛盾します。

入力例 3

5
4 3 4 3 4

出力例 3

No

入力例 4

3
2 2 2

出力例 4

Yes

入力例 5

4
2 2 2 2

出力例 5

Yes

入力例 6

5
3 3 3 3 3

出力例 6

No

Score : 700 points

Problem Statement

There are N cats. We number them from 1 through N.

Each of the cats wears a hat. Cat i says: "there are exactly a_i different colors among the N - 1 hats worn by the cats except me."

Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

Constraints

2 ≤ N ≤ 10^5
1 ≤ a_i ≤ N-1

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.

Sample Input 1

3
1 2 2

Sample Output 1

Yes

For example, if cat 1, 2 and 3 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.

Sample Input 2

3
1 1 2

Sample Output 2

No

From the remark of cat 1, we can see that cat 2 and 3 wear hats of the same color. Also, from the remark of cat 2, we can see that cat 1 and 3 wear hats of the same color. Therefore, cat 1 and 2 wear hats of the same color, which contradicts the remark of cat 3.

Sample Input 3

5
4 3 4 3 4

Sample Output 3

No

Sample Input 4

3
2 2 2

Sample Output 4

Yes

Sample Input 5

4
2 2 2 2

Sample Output 5

Yes

Sample Input 6

5
3 3 3 3 3

Sample Output 6

No

C - +/- Rectangle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

整数 H, W, h, w (1 ≤ h ≤ H, 1 ≤ w ≤ W) が与えられます。次の条件がすべて成り立つような行列が存在するか判定し、存在するならばひとつ構成してください。

行列は H 行 W 列である。
行列の各要素は -10^9 以上 10^9 以下の整数である。
行列の全要素の総和は正の値である。
どこから h 行 w 列の部分長方形を取り出しても、部分長方形に含まれる全要素の総和は負の値である。

制約

1 ≤ h ≤ H ≤ 500
1 ≤ w ≤ W ≤ 500

入力

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

H W h w

出力

条件がすべて成り立つような行列が存在しないならば、No を出力せよ。

存在するならば、1 行目に Yes を出力し、2 行目以降に行列をひとつ出力せよ。行列は以下の形式で出力せよ。ただし、a_{ij} は行列の (i,\ j) 要素を表す。

a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

入力例 1

3 3 2 2

出力例 1

行列の全要素の総和は 4 であり、正の値です。また、部分長方形を取り出す方法は次図の 4 通りですが、どの場合も、部分長方形に含まれる全要素の総和は -1 であり、負の値です。

入力例 2

2 4 1 2

出力例 2

No

入力例 3

3 4 2 3

出力例 3

Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

Score : 700 points

Problem Statement

You are given four integers: H, W, h and w (1 ≤ h ≤ H, 1 ≤ w ≤ W). Determine whether there exists a matrix such that all of the following conditions are held, and construct one such matrix if the answer is positive:

The matrix has H rows and W columns.
Each element of the matrix is an integer between -10^9 and 10^9 (inclusive).
The sum of all the elements of the matrix is positive.
The sum of all the elements within every subrectangle with h rows and w columns in the matrix is negative.

Constraints

1 ≤ h ≤ H ≤ 500
1 ≤ w ≤ W ≤ 500

Input

Input is given from Standard Input in the following format:

H W h w

Output

If there does not exist a matrix that satisfies all of the conditions, print No.

Otherwise, print Yes in the first line, and print a matrix in the subsequent lines in the following format:

a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

Here, a_{ij} represents the (i,\ j) element of the matrix.

Sample Input 1

3 3 2 2

Sample Output 1

The sum of all the elements of this matrix is 4, which is positive. Also, in this matrix, there are four subrectangles with 2 rows and 2 columns as shown below. For each of them, the sum of all the elements inside is -1, which is negative.

Sample Input 2

2 4 1 2

Sample Output 2

No

Sample Input 3

3 4 2 3

Sample Output 3

Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

D - XOR Replace

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

長さ N の数列 a = (a_1, a_2, ..., a_N) があります。ただし、各 a_i は 0 以上の整数です。

すぬけ君は次の操作を繰り返し行うことができます。

a のすべての要素の XOR を x とする。整数 i (1 ≤ i ≤ N) をひとつ選び、a_i を x に置き換える。

すぬけ君の目標は、a を数列 b = (b_1, b_2, ..., b_N) に一致させることです。ただし、各 b_i は 0 以上の整数です。

目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。

制約

2 ≤ N ≤ 10^5
a_i, b_i は整数である。
0 ≤ a_i, b_i < 2^{30}

入力

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

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

出力

目標が達成可能ならば、必要な操作回数の最小値を出力せよ。達成不可能ならば、代わりに -1 を出力せよ。

入力例 1

3
0 1 2
3 1 0

出力例 1

最初、a のすべての要素の XOR は 3 です。 a_1 を選んで 3 に置き換えると、a = (3, 1, 2) となります。

次に、a のすべての要素の XOR は 0 です。 a_3 を選んで 0 に置き換えると、a = (3, 1, 0) となり、b に一致します。

入力例 2

3
0 1 2
0 1 2

出力例 2

入力例 3

2
1 1
0 0

出力例 3

-1

入力例 4

4
0 1 2 3
1 0 3 2

出力例 4

Score : 1000 points

Problem Statement

There is a sequence of length N: a = (a_1, a_2, ..., a_N). Here, each a_i is a non-negative integer.

Snuke can repeatedly perform the following operation:

Let the XOR of all the elements in a be x. Select an integer i (1 ≤ i ≤ N) and replace a_i with x.

Snuke's objective is to match a with another sequence b = (b_1, b_2, ..., b_N). Here, each b_i is a non-negative integer.

Determine whether the objective is achievable, and find the minimum necessary number of operations if the answer is positive.

Constraints

2 ≤ N ≤ 10^5
a_i and b_i are integers.
0 ≤ a_i, b_i < 2^{30}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

Output

If the objective is achievable, print the minimum necessary number of operations. Otherwise, print -1 instead.

Sample Input 1

3
0 1 2
3 1 0

Sample Output 1

At first, the XOR of all the elements of a is 3. If we replace a_1 with 3, a becomes (3, 1, 2).

Now, the XOR of all the elements of a is 0. If we replace a_3 with 0, a becomes (3, 1, 0), which matches b.

Sample Input 2

3
0 1 2
0 1 2

Sample Output 2

Sample Input 3

2
1 1
0 0

Sample Output 3

-1

Sample Input 4

4
0 1 2 3
1 0 3 2

Sample Output 4

E - Poor Turkeys

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1400 点

問題文

N 羽の鳥がいます。鳥には 1 から N まで番号が振られています。

ここに M 人の男性が一人ずつ順番に訪れます。 i 番目に訪れる男性は次のような行動をします。

鳥 x_i, y_i が両方とも生き残っている場合 : 鳥 x_i, y_i の一方を等確率で選んで食べる。
鳥 x_i, y_i の一方のみが生き残っている場合 : 生き残っている方の鳥を食べる。
鳥 x_i, y_i がどちらも生き残っていない場合 : 何もしない。

次の条件を満たす (i,\ j) (1 ≤ i < j ≤ N) の組の個数を求めてください。

すべての男性が行動を終えた後、鳥 i, j が両方とも生き残っている確率が 0 より大きい。

制約

2 ≤ N ≤ 400
1 ≤ M ≤ 10^5
1 ≤ x_i < y_i ≤ N

入力

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

出力

条件を満たす (i,\ j) (1 ≤ i < j ≤ N) の組の個数を出力せよ。

入力例 1

3 1
1 2

出力例 1

(i,\ j) = (1,\ 3), (2,\ 3) が条件を満たします。

入力例 2

出力例 2

(i,\ j) = (1,\ 4) が条件を満たします。鳥 1, 4 が両方とも生き残るのは、次のような場合です。

1 番目の男性が鳥 2 を食べる。
2 番目の男性が鳥 3 を食べる。
3 番目の男性が何もしない。

入力例 3

3 2
1 2
1 2

出力例 3

入力例 4

出力例 4

Score : 1400 points

Problem Statement

There are N turkeys. We number them from 1 through N.

M men will visit here one by one. The i-th man to visit will take the following action:

If both turkeys x_i and y_i are alive: selects one of them with equal probability, then eats it.
If either turkey x_i or y_i is alive (but not both): eats the alive one.
If neither turkey x_i nor y_i is alive: does nothing.

Find the number of pairs (i,\ j) (1 ≤ i < j ≤ N) such that the following condition is held:

The probability of both turkeys i and j being alive after all the men took actions, is greater than 0.

Constraints

2 ≤ N ≤ 400
1 ≤ M ≤ 10^5
1 ≤ x_i < y_i ≤ N

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the number of pairs (i,\ j) (1 ≤ i < j ≤ N) such that the condition is held.

Sample Input 1

3 1
1 2

Sample Output 1

(i,\ j) = (1,\ 3), (2,\ 3) satisfy the condition.

Sample Input 2

Sample Output 2

(i,\ j) = (1,\ 4) satisfies the condition. Both turkeys 1 and 4 are alive if:

The first man eats turkey 2.
The second man eats turkey 3.
The third man does nothing.

Sample Input 3

3 2
1 2
1 2

Sample Output 3

Sample Input 4

Sample Output 4

F - Games on DAG

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 1600 点

問題文

N 頂点 M 辺の有向グラフ G があります。頂点には 1 から N まで番号が振られています。辺には 1 から M まで番号が振られています。辺 i は頂点 x_i から y_i へ張られています。ただし、x_i < y_i です。また、多重辺はありません。

G の M 本の辺集合からある部分集合を選び、G からそれらの辺を取り除いてグラフ G' を作ることを考えます。このとき、グラフ G' は 2^M 通りあり得ます。

グラフ G' の上で、高橋君と青木君が次のようなゲームで勝負します。まず、頂点 1, 2 に駒をひとつずつ置きます。高橋君から始め、高橋君と青木君が交互に次の操作を行います。

頂点 x_i に駒が置かれているような辺 i を選び、頂点 x_i の駒 (2 つある場合は一方のみ) を頂点 y_i へ移動する。 2 つの駒が同一の頂点に置かれてもよい。

先に操作を行えなくなった方が負けです。二人は最適に行動するとします。

2^M 通りの G' のうち、高橋君が勝つような G' は何通りでしょうか？ 10^9+7 で割った余りを求めてください。

制約

2 ≤ N ≤ 15
1 ≤ M ≤ N(N-1)/2
1 ≤ x_i < y_i ≤ N
(x_i,\ y_i) はすべて相異なる。

入力

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

出力

高橋君が勝つような G' は何通りか？ 10^9+7 で割った余りを出力せよ。

入力例 1

2 1
1 2

出力例 1

G' は次図の 2 通りです。高橋君が勝つ場合は ○ で、負ける場合は × で表しています。

入力例 2

出力例 2

G' は次図の 8 通りです。

入力例 3

4 2
1 3
2 4

出力例 3

入力例 4

出力例 4

Score : 1600 points

Problem Statement

There is a directed graph G with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i is directed from x_i to y_i. Here, x_i < y_i holds. Also, there are no multiple edges in G.

Consider selecting a subset of the set of the M edges in G, and removing these edges from G to obtain another graph G'. There are 2^M different possible graphs as G'.

Alice and Bob play against each other in the following game played on G'. First, place two pieces on vertices 1 and 2, one on each. Then, starting from Alice, Alice and Bob alternately perform the following operation:

Select an edge i such that there is a piece placed on vertex x_i, and move the piece to vertex y_i (if there are two pieces on vertex x_i, only move one). The two pieces are allowed to be placed on the same vertex.

The player loses when he/she becomes unable to perform the operation. We assume that both players play optimally.

Among the 2^M different possible graphs as G', how many lead to Alice's victory? Find the count modulo 10^9+7.

Constraints

2 ≤ N ≤ 15
1 ≤ M ≤ N(N-1)/2
1 ≤ x_i < y_i ≤ N
All (x_i,\ y_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the number of G' that lead to Alice's victory, modulo 10^9+7.

Sample Input 1

2 1
1 2

Sample Output 1

The figure below shows the two possible graphs as G'. A graph marked with ○ leads to Alice's victory, and a graph marked with × leads to Bob's victory.

Sample Input 2

Sample Output 2

The figure below shows the eight possible graphs as G'.

Sample Input 3

4 2
1 3
2 4

Sample Output 3

Sample Input 4