AtCoder Grand Contest 038

A - 01 Matrix

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

H 行 W 列からなるマス目があります。すぬけくんは、各マスに 0 または 1 を書き込みたいです。その際、以下の条件を全て満たす必要があります。

どの行についても、その行に含まれる 0 の個数と、その行に含まれる 1 の個数のうち、小さい方が A である。（ここで、0,1 の個数が同じ場合、小さい方はどちらとしてもよい）。
どの列についても、その列に含まれる 0 の個数と、その列に含まれる 1 の個数のうち、小さい方が B である。

これらの条件を満たすように各マスに 0,1 を書き込めるか判定し、可能な場合は条件を満たす書き込み方を 1 つ示してください。

制約

1 \leq H,W \leq 1000
0 \leq A
2 \times A \leq W
0 \leq B
2 \times B \leq H
入力される値はすべて整数である。

入力

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

H W A B

出力

条件を満たすように各マスに 0,1 を書き込むことが不可能な場合は No を出力せよ。

可能な場合は、条件を満たす書き込み方を 1 つ、以下の形式で出力せよ。

s_{11}s_{12}\cdots s_{1W}
s_{21}s_{22}\cdots s_{2W}
\vdots
s_{H1}s_{H2}\cdots s_{HW}

ただしここで s_{ij} は、マス目の上から i 行目、左から j 番目のマスに書き込む数字である。

解が複数存在する場合、どれを出力しても正解と判定される。

入力例 1

3 3 1 1

出力例 1

100
010
001

どの行についても、その行に含まれる 0,1 の個数はそれぞれ 2,1 であり、条件を満たしています。また、どの列についても、その列に含まれる 0,1 の個数はそれぞれ 2,1 であり、条件を満たしています。

入力例 2

1 5 2 0

出力例 2

Score : 300 points

Problem Statement

We have a square grid with H rows and W columns. Snuke wants to write 0 or 1 in each of the squares. Here, all of the following conditions have to be satisfied:

For every row, the smaller of the following is A: the number of 0s contained in the row, and the number of 1s contained in the row. (If these two numbers are equal, “the smaller” should be read as “either”.)
For every column, the smaller of the following is B: the number of 0s contained in the column, and the number of 1s contained in the column.

Determine if these conditions can be satisfied by writing 0 or 1 in each of the squares. If the answer is yes, show one way to fill the squares so that the conditions are satisfied.

Constraints

1 \leq H,W \leq 1000
0 \leq A
2 \times A \leq W
0 \leq B
2 \times B \leq H
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W A B

Output

If the conditions cannot be satisfied by writing 0 or 1 in each of the squares, print -1.

If the conditions can be satisfied, print one way to fill the squares so that the conditions are satisfied, in the following format:

s_{11}s_{12}\cdots s_{1W}
s_{21}s_{22}\cdots s_{2W}
\vdots
s_{H1}s_{H2}\cdots s_{HW}

Here s_{ij} is the digit written in the square at the i-th row from the top and the j-th column from the left in the grid.

If multiple solutions exist, printing any of them will be accepted.

Sample Input 1

3 3 1 1

Sample Output 1

100
010
001

Every row contains two 0s and one 1, so the first condition is satisfied. Also, every column contains two 0s and one 1, so the second condition is satisfied.

Sample Input 2

1 5 2 0

Sample Output 2

B - Sorting a Segment

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

すぬけくんは、(0,1,\cdots,N-1) の順列 (P_0,P_1,\cdots,P_{N-1}) を持っています。

すぬけくんは、以下の操作をちょうど 1 回だけ行います。

P の連続する K 要素を選び、それらを昇順に並び替える。

操作後の P としてありうる順列の個数を求めてください。

制約

2 \leq N \leq 200000
2 \leq K \leq N
0 \leq P_i \leq N-1
P_0,P_1,\cdots,P_{N-1} はすべて異なる。
入力される値はすべて整数である。

入力

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

N K
P_0 P_1 \cdots P_{N-1}

出力

操作後の P としてありうる順列の個数を出力せよ。

入力例 1

5 3
0 2 1 4 3

出力例 1

操作後の P としてありうる順列は、(0,1,2,4,3),(0,2,1,3,4) の 2 個です。

入力例 2

4 4
0 1 2 3

出力例 2

入力例 3

10 4
2 0 1 3 7 5 4 6 8 9

出力例 3

Score : 700 points

Problem Statement

Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

Choose K consecutive elements in P and sort them in ascending order.

Find the number of permutations that can be produced as P after the operation.

Constraints

2 \leq N \leq 200000
2 \leq K \leq N
0 \leq P_i \leq N-1
P_0,P_1,\cdots,P_{N-1} are all different.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

C - LCMs

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A_0,A_1,\cdots,A_{N-1} があります。次式の値を求めてください。

\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)

ここで、\mathrm{lcm}(x,y) は、x と y の最小公倍数を意味します。なお、答えは非常に大きくなることがあるので、998244353 で割ったあまりを求めてください。

制約

1 \leq N \leq 200000
1 \leq A_i \leq 1000000
入力される値はすべて整数である。

入力

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

N
A_0\ A_1\ \cdots\ A_{N-1}

出力

\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j) の値を 998244353 で割ったあまりを出力せよ。

入力例 1

3
2 4 6

出力例 1

\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22 です。

入力例 2

8
1 2 3 4 6 8 12 12

出力例 2

入力例 3

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

出力例 3

353891724

Score : 700 points

Problem Statement

We have an integer sequence of length N: A_0,A_1,\cdots,A_{N-1}.

Find the following sum (\mathrm{lcm}(a, b) denotes the least common multiple of a and b):

\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)

Since the answer may be enormous, compute it modulo 998244353.

Constraints

1 \leq N \leq 200000
1 \leq A_i \leq 1000000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0\ A_1\ \cdots\ A_{N-1}

Output

Print the sum modulo 998244353.

Sample Input 1

3
2 4 6

Sample Output 1

\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22.

Sample Input 2

8
1 2 3 4 6 8 12 12

Sample Output 2

Sample Input 3

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

Sample Output 3

353891724

D - Unique Path

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

すぬけ君は、0 から N-1 までの番号のついた N 個の頂点と、M 本の辺からなる無向グラフをお母さんにもらいました。このグラフは連結で、また、多重辺や自己ループは存在しませんでした。

ある日、すぬけ君はこのグラフを壊してしまいました。しかし、すぬけ君はこのグラフについて、Q 個の情報を覚えています。 i (0 \leq i \leq Q-1) 番目の情報は整数 A_i,B_i,C_i で表され、次のことを意味します。

C_i=0 の時: 頂点 A_i から B_i に向かう単純パス（同じ頂点を 2 度通らないパス）が、1 つしか存在しない。
C_i=1 の時: 頂点 A_i から B_i に向かう単純パスが 2 つ以上存在する。

すぬけ君は自分の記憶に自信がないので、これら Q 個の情報に合致するグラフが存在するのかどうか心配になりました。すぬけくんの記憶に合致するグラフが存在するかどうか判定してください。

制約

2 \leq N \leq 10^5
N-1 \leq M \leq N \times (N-1)/2
1 \leq Q \leq 10^5
0 \leq A_i,B_i \leq N-1
A_i \neq B_i
0 \leq C_i \leq 1
入力される値はすべて整数である。

入力

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

N M Q
A_0 B_0 C_0
A_1 B_1 C_1
\vdots
A_{Q-1} B_{Q-1} C_{Q-1}

出力

すぬけくんの記憶に合致するグラフが存在する場合は Yes、そうでない場合は No と出力せよ。

入力例 1

出力例 1

Yes

例えば、辺集合が (0,1),(1,2),(1,4),(2,3),(2,4) であるグラフを考えると、これは条件を満たします。

入力例 2

出力例 2

No

入力例 3

出力例 3

No

Score : 700 points

Problem Statement

Snuke's mother gave Snuke an undirected graph consisting of N vertices numbered 0 to N-1 and M edges. This graph was connected and contained no parallel edges or self-loops.

One day, Snuke broke this graph. Fortunately, he remembered Q clues about the graph. The i-th clue (0 \leq i \leq Q-1) is represented as integers A_i,B_i,C_i and means the following:

If C_i=0: there was exactly one simple path (a path that never visits the same vertex twice) from Vertex A_i to B_i.
If C_i=1: there were two or more simple paths from Vertex A_i to B_i.

Snuke is not sure if his memory is correct, and worried whether there is a graph that matches these Q clues. Determine if there exists a graph that matches Snuke's memory.

Constraints

2 \leq N \leq 10^5
N-1 \leq M \leq N \times (N-1)/2
1 \leq Q \leq 10^5
0 \leq A_i,B_i \leq N-1
A_i \neq B_i
0 \leq C_i \leq 1
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
A_0 B_0 C_0
A_1 B_1 C_1
\vdots
A_{Q-1} B_{Q-1} C_{Q-1}

Output

If there exists a graph that matches Snuke's memory, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

For example, consider a graph with edges (0,1),(1,2),(1,4),(2,3),(2,4). This graph matches the clues.

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

No

E - Gachapon

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

すぬけくんはある乱数生成器を手に入れました。この乱数生成器は、0 以上 N-1 以下の整数を生成します。それぞれの整数を生成する確率は、整数列 A_0,A_1,\cdots,A_{N-1} によって表され、整数 i (0 \leq i \leq N-1) が生成される確率は A_i / S です。ただしここで S = \sum_{i=0}^{N-1} A_i とします。また、乱数生成は毎回独立に行われます。

すぬけくんはこれから、次の条件が満たされるまで、乱数生成を繰り返します。

すべての i (0 \leq i \leq N-1) について、今までに乱数生成器が i を生成した回数が B_i 回以上である。

すぬけくんが操作を行う回数の期待値を求めてください。ただし、期待値は mod 998244353 で出力してください。より正確には、期待値が既約分数 P/Q で表されるとき、 R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353 を満たす整数 R が一意に定まるので、その R を出力してください。

なお、操作の回数の期待値が有理数として存在し、さらに mod 998244353 での整数表現が定義できることが問題の制約から証明できます。

制約

1 \leq N \leq 400
1 \leq A_i
\sum_{i=0}^{N-1} A_i \leq 400
1 \leq B_i
\sum_{i=0}^{N-1} B_i \leq 400
入力される値はすべて整数である。

入力

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

N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

すぬけくんが操作を行う回数の期待値を mod 998244353 で出力せよ。

入力例 1

2
1 1
1 1

出力例 1

すぬけくんが操作を行う回数の期待値は 3 です。

入力例 2

出力例 2

971485877

すぬけくんが操作を行う回数の期待値は 132929/7200 です。

入力例 3

出力例 3

371626143

Score : 1600 points

Problem Statement

Snuke found a random number generator. It generates an integer between 0 and N-1 (inclusive). An integer sequence A_0, A_1, \cdots, A_{N-1} represents the probability that each of these integers is generated. The integer i (0 \leq i \leq N-1) is generated with probability A_i / S, where S = \sum_{i=0}^{N-1} A_i. The process of generating an integer is done independently each time the generator is executed.

Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:

For every i (0 \leq i \leq N-1), the integer i has been generated at least B_i times so far.

Find the expected number of times Snuke will generate an integer, and print it modulo 998244353. More formally, represent the expected number of generations as an irreducible fraction P/Q. Then, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353, so print this R.

From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo 998244353 can be defined.

Constraints

1 \leq N \leq 400
1 \leq A_i
\sum_{i=0}^{N-1} A_i \leq 400
1 \leq B_i
\sum_{i=0}^{N-1} B_i \leq 400
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Print the expected number of times Snuke will generate an integer, modulo 998244353.

Sample Input 1

2
1 1
1 1

Sample Output 1

The expected number of times Snuke will generate an integer is 3.

Sample Input 2

Sample Output 2

971485877

The expected number of times Snuke will generate an integer is 132929/7200.

Sample Input 3

Sample Output 3

371626143

F - Two Permutations

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

すぬけくんは、(0,1,\cdots,N-1) の順列 (P_0,P_1,\cdots,P_{N-1}) と (Q_0,Q_1,\cdots,Q_{N-1}) を持っています。

すぬけくんはこれから、(0,1,\cdots,N-1) の順列 A および B を、以下の条件を満たすように作ります。

それぞれの i (0 \leq i \leq N-1) について、A_i は i または P_i である。
それぞれの i (0 \leq i \leq N-1) について、B_i は i または Q_i である。

順列 A と B の距離を、A_i \neq B_i となる i の個数と定義します。 A と B の距離の最大値を求めてください。

制約

1 \leq N \leq 100000
0 \leq P_i \leq N-1
P_0,P_1,\cdots,P_{N-1} はすべて異なる。
0 \leq Q_i \leq N-1
Q_0,Q_1,\cdots,Q_{N-1} はすべて異なる。
入力される値はすべて整数である。

入力

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

N
P_0 P_1 \cdots P_{N-1}
Q_0 Q_1 \cdots Q_{N-1}

出力

順列 A と B の距離の最大値を出力せよ。

入力例 1

4
2 1 3 0
0 2 3 1

出力例 1

例えば、A=(0,1,2,3),\ B=(0,2,3,1) とすると距離が 3 になり、これが最大です。

入力例 2

10
0 4 5 3 7 8 2 1 9 6
3 8 5 6 4 0 2 1 7 9

出力例 2

入力例 3

32
22 31 30 29 7 17 16 3 14 9 19 11 2 5 10 1 25 18 15 24 20 0 12 21 27 4 26 28 8 6 23 13
22 3 2 7 17 9 16 4 14 8 19 26 28 5 10 1 25 18 15 13 11 0 12 23 21 20 29 24 27 6 30 31

出力例 3

Score : 1600 points

Problem Statement

Snuke has permutations (P_0,P_1,\cdots,P_{N-1}) and (Q_0,Q_1,\cdots,Q_{N-1}) of (0,1,\cdots,N-1).

Now, he will make new permutations A and B of (0,1,\cdots,N-1), under the following conditions:

For each i (0 \leq i \leq N-1), A_i should be i or P_i.
For each i (0 \leq i \leq N-1), B_i should be i or Q_i.

Let us define the distance of permutations A and B as the number of indices i such that A_i \neq B_i. Find the maximum possible distance of A and B.

Constraints

1 \leq N \leq 100000
0 \leq P_i \leq N-1
P_0,P_1,\cdots,P_{N-1} are all different.
0 \leq Q_i \leq N-1
Q_0,Q_1,\cdots,Q_{N-1} are all different.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_0 P_1 \cdots P_{N-1}
Q_0 Q_1 \cdots Q_{N-1}

Output

Print the maximum possible distance of A and B.

Sample Input 1

4
2 1 3 0
0 2 3 1

Sample Output 1

For example, if we make A=(0,1,2,3) and B=(0,2,3,1), the distance will be 3, which is the maximum result possible.

Sample Input 2

10
0 4 5 3 7 8 2 1 9 6
3 8 5 6 4 0 2 1 7 9

Sample Output 2

Sample Input 3

32
22 31 30 29 7 17 16 3 14 9 19 11 2 5 10 1 25 18 15 24 20 0 12 21 27 4 26 28 8 6 23 13
22 3 2 7 17 9 16 4 14 8 19 26 28 5 10 1 25 18 15 13 11 0 12 23 21 20 29 24 27 6 30 31