AtCoder Grand Contest 008

A - Simple Calculator

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

すぬけ君は電卓を持っています。この電卓にはディスプレイと 2 個のボタンが付いています。

最初、ディスプレイの値は整数 x です。すぬけ君の目標は、ディスプレイの値を整数 y にすることです。そのために、すぬけ君は次の 2 個のボタンを好きな順番で何回か押すことができます。

ボタン A : ディスプレイの値を 1 増やす。
ボタン B : ディスプレイの値の符号を反転する。

目標を達成するためにすぬけ君がボタンを押す回数の最小値を求めてください。なお、整数 x, y の値によらず、必ず目標を達成できることが示せます。

制約

x, y は整数である。
|x|, |y| ≤ 10^9
x, y は相異なる。

入力

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

x y

出力

目標を達成するためにすぬけ君がボタンを押す回数の最小値を出力せよ。

入力例 1

10 20

出力例 1

ボタン A を 10 回押せばよいです。

入力例 2

10 -10

出力例 2

ボタン B を 1 回押せばよいです。

入力例 3

-10 -20

出力例 3

次の順でボタンを押せばよいです。

ボタン B を 1 回押す。
ボタン A を 10 回押す。
ボタン B を 1 回押す。

Score : 300 points

Problem Statement

Snuke has a calculator. It has a display and two buttons.

Initially, the display shows an integer x. Snuke wants to change this value into another integer y, by pressing the following two buttons some number of times in arbitrary order:

Button A: When pressed, the value on the display is incremented by 1.
Button B: When pressed, the sign of the value on the display is reversed.

Find the minimum number of times Snuke needs to press the buttons to achieve his objective. It can be shown that the objective is always achievable regardless of the values of the integers x and y.

Constraints

x and y are integers.
|x|, |y| ≤ 10^9
x and y are different.

Input

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

x y

Output

Print the minimum number of times Snuke needs to press the buttons to achieve his objective.

Sample Input 1

10 20

Sample Output 1

Press button A ten times.

Sample Input 2

10 -10

Sample Output 2

Press button B once.

Sample Input 3

-10 -20

Sample Output 3

Press the buttons as follows:

Press button B once.
Press button A ten times.
Press button B once.

B - Contiguous Repainting

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

N 個のマスが横一列に並んでいます。左から i 番目のマスには整数 a_i が書かれています。

最初、すべてのマスは白色です。すぬけ君は次の操作を好きな回数だけ繰り返します。

連続する K 個のマスを選び、それらすべてを白く塗るか、それらすべてを黒く塗る。このとき、各マスの色は上書きされる。

すぬけ君が操作を終えた後、黒いマスに書かれた整数の総和がスコアになります。考えられるスコアの最大値を求めてください。

制約

1≤N≤10^5
1≤K≤N
a_i は整数である。
|a_i|≤10^9

入力

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

N K
a_1 a_2 ... a_N

出力

考えられるスコアの最大値を出力せよ。

入力例 1

5 3
-10 10 -10 10 -10

出力例 1

左から 2, 3, 4 番目のマスを黒く塗ればよいです。

入力例 2

4 2
10 -10 -10 10

出力例 2

たとえば、次のように操作を行えばよいです。

左から 1, 2 番目のマスを黒く塗る。
左から 3, 4 番目のマスを黒く塗る。
左から 2, 3 番目のマスを白く塗る。

入力例 3

1 1
-10

出力例 3

入力例 4

10 5
5 -4 -5 -8 -4 7 2 -4 0 7

出力例 4

Score : 400 points

Problem Statement

There are N squares aligned in a row. The i-th square from the left contains an integer a_i.

Initially, all the squares are white. Snuke will perform the following operation some number of times:

Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten.

After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares. Find the maximum possible score.

Constraints

1≤N≤10^5
1≤K≤N
a_i is an integer.
|a_i|≤10^9

Input

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

N K
a_1 a_2 ... a_N

Output

Print the maximum possible score.

Sample Input 1

5 3
-10 10 -10 10 -10

Sample Output 1

Paint the following squares black: the second, third and fourth squares from the left.

Sample Input 2

4 2
10 -10 -10 10

Sample Output 2

One possible way to obtain the maximum score is as follows:

Paint the following squares black: the first and second squares from the left.
Paint the following squares black: the third and fourth squares from the left.
Paint the following squares white: the second and third squares from the left.

Sample Input 3

1 1
-10

Sample Output 3

Sample Input 4

10 5
5 -4 -5 -8 -4 7 2 -4 0 7

Sample Output 4

C - Tetromino Tiling

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

正方形のマスを 4 個繋げた形をテトロミノといいます。次の 7 種類のテトロミノを順に I, O, T, J, L, S, Z 型と呼ぶことにします。

すぬけ君は I, O, T, J, L, S, Z 型のテトロミノをそれぞれ a_I, a_O, a_T, a_J, a_L, a_S, a_Z 個ずつ持っています。すぬけ君はこれらのテトロミノのうち K 個を組み合わせ、縦 2 マス、横 2K マスの長方形を作ろうとしています。このとき、すぬけ君は次のルールに従います。

各テトロミノを置くとき、回転はできるが、反転はできない。
長方形の各マスにはちょうど 1 個のテトロミノが置かれているようにする。
長方形の外部にテトロミノが置かれていないようにする。

すぬけ君はできるだけ大きい長方形を作ろうとしています。 K の最大値を求めてください。

制約

0≤a_I,a_O,a_T,a_J,a_L,a_S,a_Z≤10^9
a_I+a_O+a_T+a_J+a_L+a_S+a_Z≥1

入力

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

a_I a_O a_T a_J a_L a_S a_Z

出力

K の最大値を出力せよ。長方形を作ることができない場合、0 を出力せよ。

入力例 1

2 1 1 0 0 0 0

出力例 1

たとえば、図のように組み合わせればよいです。

入力例 2

0 0 10 0 0 0 0

出力例 2

長方形を作ることができません。

Score : 600 points

Problem Statement

A tetromino is a figure formed by joining four squares edge to edge. We will refer to the following seven kinds of tetromino as I-, O-, T-, J-, L-, S- and Z-tetrominos, respectively:

Snuke has many tetrominos. The number of I-, O-, T-, J-, L-, S- and Z-tetrominos in his possession are a_I, a_O, a_T, a_J, a_L, a_S and a_Z, respectively. Snuke will join K of his tetrominos to form a rectangle that is two squares tall and 2K squares wide. Here, the following rules must be followed:

When placing each tetromino, rotation is allowed, but reflection is not.
Each square in the rectangle must be covered by exactly one tetromino.
No part of each tetromino may be outside the rectangle.

Snuke wants to form as large a rectangle as possible. Find the maximum possible value of K.

Constraints

0≤a_I,a_O,a_T,a_J,a_L,a_S,a_Z≤10^9
a_I+a_O+a_T+a_J+a_L+a_S+a_Z≥1

Input

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

a_I a_O a_T a_J a_L a_S a_Z

Output

Print the maximum possible value of K. If no rectangle can be formed, print 0.

Sample Input 1

2 1 1 0 0 0 0

Sample Output 1

One possible way to form the largest rectangle is shown in the following figure:

Sample Input 2

0 0 10 0 0 0 0

Sample Output 2

No rectangle can be formed.

D - K-th K

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

長さ N の数列 x が与えられます。次の条件をすべて満たす数列 a が存在するか判定し、存在するならば a を 1 つ構成してください。

a は長さ N^2 であり、整数 1, 2, ..., N をそれぞれちょうど N 個ずつ含む。
各 1 ≤ i ≤ N について、a に含まれる整数 i のうち左から i 番目に位置するものは、a 全体では左から x_i 番目に位置する。

制約

1 ≤ N ≤ 500
1 ≤ x_i ≤ N^2
x_i はすべて相異なる。

入力

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

N
x_1 x_2 ... x_N

出力

条件をすべて満たす数列 a が存在しないならば、No を出力せよ。存在するならば、1 行目に Yes を出力し、2 行目に a を空白区切りで出力せよ。

入力例 1

3
1 5 9

出力例 1

Yes
1 1 1 2 2 2 3 3 3

たとえば、a に含まれる整数 2 のうち左から 2 番目に位置するものは、a 全体では左から 5 番目に位置しています。整数 1, 3 についても同様に条件が成り立っています。

入力例 2

2
4 1

出力例 2

No

Score : 800 points

Problem Statement

You are given an integer sequence x of length N. Determine if there exists an integer sequence a that satisfies all of the following conditions, and if it exists, construct an instance of a.

a is N^2 in length, containing N copies of each of the integers 1, 2, ..., N.
For each 1 ≤ i ≤ N, the i-th occurrence of the integer i from the left in a is the x_i-th element of a from the left.

Constraints

1 ≤ N ≤ 500
1 ≤ x_i ≤ N^2
All x_i are distinct.

Input

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

N
x_1 x_2 ... x_N

Output

If there does not exist an integer sequence a that satisfies all the conditions, print No. If there does exist such an sequence a, print Yes in the first line, then print an instance of a in the second line, with spaces inbetween.

Sample Input 1

3
1 5 9

Sample Output 1

Yes
1 1 1 2 2 2 3 3 3

For example, the second occurrence of the integer 2 from the left in a in the output is the fifth element of a from the left. Similarly, the condition is satisfied for the integers 1 and 3.

Sample Input 2

2
4 1

Sample Output 2

No

E - Next or Nextnext

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1400 点

問題文

長さ N の数列 a が与えられます。 1 から N までの整数の順列 p であって、次の条件を満たすものは何通りでしょうか？ 10^9 + 7 で割った余りを求めてください。

各 1 ≤ i ≤ N について、p_i = a_i または p_{p_i} = a_i の少なくとも一方が成り立つ。

制約

1 ≤ N ≤ 10^5
a_i は整数である。
1 ≤ a_i ≤ N

入力

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

N
a_1 a_2 ... a_N

出力

条件を満たす順列 p の個数を 10^9 + 7 で割った余りを出力せよ。

入力例 1

3
1 2 3

出力例 1

次の 4 通りです。

(1, 2, 3)
(1, 3, 2)
(3, 2, 1)
(2, 1, 3)

たとえば (1, 3, 2) は、p_1 = 1, p_{p_2} = 2, p_{p_3} = 3 となっています。

入力例 2

2
1 1

出力例 2

次の 1 通りです。

(2, 1)

入力例 3

3
2 1 1

出力例 3

次の 2 通りです。

(2, 3, 1)
(3, 1, 2)

入力例 4

3
1 1 1

出力例 4

入力例 5

13
2 1 4 3 6 7 5 9 10 8 8 9 11

出力例 5

Score : 1400 points

Problem Statement

You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?

For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.

Find the count modulo 10^9 + 7.

Constraints

1 ≤ N ≤ 10^5
a_i is an integer.
1 ≤ a_i ≤ N

Input

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

N
a_1 a_2 ... a_N

Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Sample Input 1

3
1 2 3

Sample Output 1

The following four permutations satisfy the condition:

(1, 2, 3)
(1, 3, 2)
(3, 2, 1)
(2, 1, 3)

For example, (1, 3, 2) satisfies the condition because p_1 = 1, p_{p_2} = 2 and p_{p_3} = 3.

Sample Input 2

2
1 1

Sample Output 2

The following one permutation satisfies the condition:

(2, 1)

Sample Input 3

3
2 1 1

Sample Output 3

The following two permutations satisfy the condition:

(2, 3, 1)
(3, 1, 2)

Sample Input 4

3
1 1 1

Sample Output 4

Sample Input 5

13
2 1 4 3 6 7 5 9 10 8 8 9 11

Sample Output 5

F - Black Radius

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1900 点

問題文

N 頂点の木があります。頂点は 1 から N まで番号が振られています。各 1 ≤ i ≤ N - 1 について、i 番目の辺は頂点 a_i と b_i を繋いでいます。辺の長さはすべて 1 です。

いくつかの頂点はすぬけ君のお気に入りです。お気に入りの頂点の情報は、長さ N の文字列 s として与えられます。各 1 ≤ i ≤ N について、頂点 i がお気に入りならば s_i は 1 で、頂点 i がお気に入りでないならば s_i は 0 です。

最初、頂点はすべて白色です。すぬけ君は次の操作をちょうど 1 回だけ行います。

お気に入りの頂点 v をひとつ選び、非負整数 d をひとつ選ぶ。頂点 v から距離 d 以内の頂点をすべて黒く塗る。

最終的な頂点の色の組合せとして考えられるものは何通りか求めてください。

制約

2 ≤ N ≤ 2×10^5
1 ≤ a_i, b_i ≤ N
グラフは木である。
|s| = N
s は 0 と 1 のみからなる。
s には 1 が含まれる。

部分点

1300 点分のデータセットでは、s は 1 のみからなる。

入力

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

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s

出力

最終的な頂点の色の組合せとして考えられるものは何通りか出力せよ。

入力例 1

出力例 1

次の 4 通りです。

入力例 2

出力例 2

このケースは部分点の制約を満たします。

入力例 3

出力例 3

Score : 1900 points

Problem Statement

There is a tree with N vertices. The vertices are numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i. The lengths of all the edges are 1.

Snuke likes some of the vertices. The information on his favorite vertices are given to you as a string s of length N. For each 1 ≤ i ≤ N, s_i is 1 if Snuke likes vertex i, and 0 if he does not like vertex i.

Initially, all the vertices are white. Snuke will perform the following operation exactly once:

Select a vertex v that he likes, and a non-negative integer d. Then, paint all the vertices black whose distances from v are at most d.

Find the number of the possible combinations of colors of the vertices after the operation.

Constraints

2 ≤ N ≤ 2×10^5
1 ≤ a_i, b_i ≤ N
The given graph is a tree.
|s| = N
s consists of 0 and 1.
s contains at least one occurrence of 1.

Partial Score

In the test set worth 1300 points, s consists only of 1.

Input

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

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s

Output

Print the number of the possible combinations of colors of the vertices after the operation.

Sample Input 1

Sample Output 1

The following four combinations of colors of the vertices are possible:

Sample Input 2

Sample Output 2

This case satisfies the additional constraint for the partial score.

Sample Input 3