AtCoder Grand Contest 046

A - Takahashikun, The Strider

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

平面上に高橋君がおり、真北を向いて立っています。高橋君が以下の行動を K 回繰り返したときに元の位置に戻ってくるような最小の正の整数 K を求めてください。

今向いている方向に 1 メートル進む。その後、向いている方向を反時計回りに X 度だけ回転させる。

制約

1 \leq X \leq 179
X は整数である

入力

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

出力

条件を満たす最小の正の整数 K を出力せよ。

入力例 1

出力例 1

高橋君は正方形状の軌道を描きます。

入力例 2

出力例 2

Score : 200 points

Problem Statement

Takahashi is standing on a two-dimensional plane, facing north. Find the minimum positive integer K such that Takahashi will be at the starting position again after he does the following action K times:

Go one meter in the direction he is facing. Then, turn X degrees counter-clockwise.

Constraints

1 \leq X \leq 179
X is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the number of times Takahashi will do the action before he is at the starting position again.

Sample Input 1

Sample Output 1

Takahashi's path is a square.

Sample Input 2

Sample Output 2

B - Extension

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

縦 A マス横 B マスのマス目があり、そのすべてのマスは白く塗られています。このマス目に、以下の操作を繰り返し行います。

現在のマス目が縦 a マス横 b マスであるとする。縦または横を選ぶ。
- 縦を選んだ場合はマス目の上に 1 行を追加し、縦 a+1 マス横 b マスのマス目にする。
- 横を選んだ場合はマス目の右に 1 列を追加し、縦 a マス横 b+1 マスのマス目にする。
これにより追加されたマスのうちちょうど 1 マスを黒く塗り、追加された残りのマスを白く塗る。

最終的にマス目が縦 C マス横 D マスになったとするとき、最終的なマス目の異なる塗られ方としてありうるものの個数を 998244353 で割った余りを求めてください。

制約

1 \leq A \leq C \leq 3000
1 \leq B \leq D \leq 3000
A,B,C,D は整数である

入力

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

A B C D

出力

最終的なマス目の異なる塗られ方としてありうるものの個数を 998244353 で割った余りを出力せよ。

入力例 1

1 1 2 2

出力例 1

左下以外の 3 マスの中の任意の 2 マスが黒く塗られているような塗られ方が条件を満たします。

入力例 2

2 1 3 4

出力例 2

入力例 3

31 41 59 265

出力例 3

387222020

Score : 600 points

Problem Statement

We have a grid with A horizontal rows and B vertical columns, with the squares painted white. On this grid, we will repeatedly apply the following operation:

Assume that the grid currently has a horizontal rows and b vertical columns. Choose "vertical" or "horizontal".
- If we choose "vertical", insert one row at the top of the grid, resulting in an (a+1) \times b grid.
- If we choose "horizontal", insert one column at the right end of the grid, resulting in an a \times (b+1) grid.
Then, paint one of the added squares black, and the other squares white.

Assume the grid eventually has C horizontal rows and D vertical columns. Find the number of ways in which the squares can be painted in the end, modulo 998244353.

Constraints

1 \leq A \leq C \leq 3000
1 \leq B \leq D \leq 3000
A, B, C, and D are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of ways in which the squares can be painted in the end, modulo 998244353.

Sample Input 1

1 1 2 2

Sample Output 1

Any two of the three squares other than the bottom-left square can be painted black.

Sample Input 2

2 1 3 4

Sample Output 2

Sample Input 3

31 41 59 265

Sample Output 3

387222020

C - Shift

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

0 と 1 のみからなる文字列 S が与えられます。S に以下の操作を 0 回以上 K 回以下繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを求めてください。

整数 1\leq i < j\leq |S| の組であって、S の i 文字目が 0 であり j 文字目が 1 であるものを選ぶ。S の j 文字目を取り除き、i 文字目の直前の位置に挿入する。

制約

1 \leq |S| \leq 300
0 \leq K \leq 10^9
S は 0, 1 のみからなる

入力

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

S K

出力

S に操作を 0 回以上 K 回以下繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを出力せよ。

入力例 1

0101 1

出力例 1

0101, 0110, 1001, 1010 の 4 通りの文字列ができる可能性があります。

入力例 2

01100110 2

出力例 2

入力例 3

1101010010101101110111100011011111011000111101110101010010101010101 20

出力例 3

113434815

Score : 800 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are 0 and 1, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

1 \leq |S| \leq 300
0 \leq K \leq 10^9
S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S K

Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Sample Input 1

0101 1

Sample Output 1

Four strings, 0101, 0110, 1001, and 1010, can result.

Sample Input 2

01100110 2

Sample Output 2

Sample Input 3

1101010010101101110111100011011111011000111101110101010010101010101 20

Sample Output 3

113434815

D - Secret Passage

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

0 と 1 のみからなる文字列 S が与えられます。以下の操作を 0 回以上任意の回数繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを求めてください。

S の先頭 2 文字を取り除き、そのうち片方を捨て、もう片方を S の任意の位置に挿入する。この操作は、S が 2 文字以上からなるときのみ実行できる。

制約

1 \leq |S| \leq 300
S は 0 と 1 のみからなる

入力

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

出力

操作を 0 回以上任意の回数繰り返してできる可能性のある文字列の個数を 998244353 で割った余りを出力せよ。

入力例 1

出力例 1

0001, 001, 010, 00, 01, 10, 0, 1 の 8 つが条件を満たします。

入力例 2

出力例 2

入力例 3

11101111011111000000000110000001111100011111000000001111111110000000111111111

出力例 3

697354558

Score : 1100 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S zero or more times:

Remove the two characters at the beginning of S, erase one of them, and reinsert the other somewhere in S. This operation can be applied only when S has two or more characters.

Constraints

1 \leq |S| \leq 300
S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Sample Input 1

Sample Output 1

Eight strings, 0001, 001, 010, 00, 01, 10, 0, and 1, can result.

Sample Input 2

Sample Output 2

Sample Input 3

11101111011111000000000110000001111100011111000000001111111110000000111111111

Sample Output 3

697354558

E - Permutation Cover

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

整数 K と整数 a_1,\dots, a_K が与えられます。以下を満たす数列 P が存在するか判定し、存在する場合は辞書順最小のものを求めてください。

P のすべての項は 1 以上 K 以下の整数である
各 i=1,\dots, K に対し、P は i を a_i 個含む
P の各項について、その項を含むある長さ K の連続する部分列が存在し、1,\dots, K の並び替えになっている

制約

1 \leq K \leq 100
1 \leq a_i \leq 1000 \quad (1\leq i\leq K)
a_1 + \dots + a_K\leq 1000
入力はすべて整数である

入力

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

K
a_1 a_2 \dots a_K

出力

条件を満たす数列が存在しない場合、-1 を出力せよ。そうでない場合、条件を満たす辞書順最小の数列を出力せよ。

入力例 1

3
2 4 3

出力例 1

2 1 3 2 2 3 1 2 3

例えば、5 項目の 2 は、5,6,7 項目からなる部分列 (2,3,1) に含まれます。

入力例 2

4
3 2 3 2

出力例 2

1 2 3 4 1 3 1 2 4 3

入力例 3

5
3 1 4 1 5

出力例 3

-1

Score : 1500 points

Problem Statement

Given are an integer K and integers a_1,\dots, a_K. Determine whether a sequence P satisfying below exists. If it exists, find the lexicographically smallest such sequence.

Every term in P is an integer between 1 and K (inclusive).
For each i=1,\dots, K, P contains a_i occurrences of i.
For each term in P, there is a contiguous subsequence of length K that contains that term and is a permutation of 1,\dots, K.

Constraints

1 \leq K \leq 100
1 \leq a_i \leq 1000 \quad (1\leq i\leq K)
a_1 + \dots + a_K\leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

K
a_1 a_2 \dots a_K

Output

If there is no sequence satisfying the conditions, print -1. Otherwise, print the lexicographically smallest sequence satisfying the conditions.

Sample Input 1

3
2 4 3

Sample Output 1

2 1 3 2 2 3 1 2 3

For example, the fifth term, which is 2, is in the subsequence (2, 3, 1) composed of the fifth, sixth, and seventh terms.

Sample Input 2

4
3 2 3 2

Sample Output 2

1 2 3 4 1 3 1 2 4 3

Sample Input 3

5
3 1 4 1 5

Sample Output 3

-1

F - Forbidden Tournament

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 2000 点

問題文

整数 N,K と素数 P が与えられます。N 頂点の有向グラフ G であって、以下を全て満たすものの個数を P で割った余りを求めてください。ただし、頂点どうしは互いに区別します。

G はトーナメントである。すなわち、G に多重辺や自己ループはなく、G のどの 2 点 u,v に対しても、u\to v 辺または v\to u 辺のうちちょうど片方が存在する。
G のどの頂点の入次数も K 以下である。
G のどの相異なる 4 頂点 a,b,c,d に対しても、a\to b, b\to c, c\to a, a\to d, b\to d, c\to d の 6 辺がすべて同時に存在することはない。

制約

4 \leq N \leq 200
\frac{N-1}{2} \leq K \leq N-1
10^8<P<10^9
N,K は整数である
P は素数である

入力

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

N K P

出力

条件を満たす有向グラフの個数を P で割った余りを出力せよ。

入力例 1

4 3 998244353

出力例 1

4 頂点のグラフ 64 個のうち、禁止された誘導部分グラフと同型である 8 個を除いた 56 個が条件を満たします。

入力例 2

7 3 998244353

出力例 2

入力例 3

50 37 998244353

出力例 3

495799508

Score : 2000 points

Problem Statement

Given are integers N and K, and a prime number P. Find the number, modulo P, of directed graphs G with N vertices that satisfy below. Here, the vertices are distinguishable from each other.

G is a tournament, that is, G contains no duplicated edges or self-loops, and exactly one of the edges u\to v and v\to u exists for any two vertices u and v.
The in-degree of every vertex in G is at most K.
For any four distinct vertices a, b, c, and d in G, it is not the case that all of the six edges a\to b, b\to c, c\to a, a\to d, b\to d, and c\to d exist simultaneously.

Constraints

4 \leq N \leq 200
\frac{N-1}{2} \leq K \leq N-1
10^8<P<10^9
N and K are integers.
P is a prime number.

Input

Input is given from Standard Input in the following format:

N K P

Output

Print the number of directed graphs that satisfy the conditions, modulo P.

Sample Input 1

4 3 998244353

Sample Output 1

Among the 64 graphs with four vertices, 8 are isomorphic to the forbidden induced subgraphs, and the other 56 satisfy the conditions.

Sample Input 2

7 3 998244353

Sample Output 2

Sample Input 3

50 37 998244353

Sample Output 3

495799508