AtCoder Regular Contest 115

A - Two Choices

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

0 か 1 で答える問題 M 問からなるテストがあり、これに N 人の生徒が取り組みました。 N 個の長さ M の文字列 S_1,S_2,\ldots,S_N が与えられます。 S_i の k 文字目は 0 と 1 のいずれかであり、 i 番目の生徒の k 問目に対する解答を示しています。各生徒の各問題に対する解答は判明していますが、各問題の正解が 0 と 1 のどちらであるかはまだ判明していません。 1 \leq i < j \leq N を満たす組 (i,j) であって、生徒 i と生徒 j の正解した問題の数が等しい可能性がないようなものはいくつあるか求めてください。

制約

2 \leq N \leq 10^5
1 \leq M \leq 20
S_i は 0 と 1 からなる長さ M の文字列

入力

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

N M
S_1
S_2
:
S_N

出力

答えを出力せよ。

入力例 1

出力例 1

例えば 1 問目の正解と 2 問目の正解が共に 0 のとき、生徒 2 と生徒 3 の正解数は共に 1 となり等しくなります。一方、生徒 1 と生徒 2 のペア、生徒 1 と生徒 3 のペアでは、二人の正解数が等しいことはありません。

入力例 2

出力例 2

Score : 300 points

Problem Statement

N students took a test with M questions with two choices: 0 and 1. You are given N strings of length M each: S_1, S_2, \ldots, S_N. The k-th character of S_i is 0 or 1, representing the response of the i-th student to the k-th question. Although we know the response of each student to each question, we do not yet know the correct answer ― 0 or 1 ― to each problem. Find the number of pairs (i, j) satisfying 1 \leq i < j \leq N such that it is impossible for Student i and Student j to have the same number of correct answers.

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 20
S_i is a string of length M consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
:
S_N

Output

Print the answer.

Sample Input 1

Sample Output 1

For example, if the correct answers to the 1-st and 2-nd questions are both 0, Student 2 and Student 3 have the same number of correct answers ― 1. On the other hand, Student 1 and Student 2 never have the same number of correct answers, nor do Student 1 and Student 3.

Sample Input 2

Sample Output 2

B - Plus Matrix

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 行 N 列の非負整数を成分とする行列 C が与えられます。すべての (i,j) について C_{i,j}=A_i+B_j を満たすような非負整数列 A_1,A_2,\ldots,A_N と B_1,B_2,\ldots,B_N の組が存在するか判定し、存在するなら一つ出力してください。

制約

1 \leq N \leq 500
0 \leq C_{i,j} \leq 10^9

入力

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

N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
:
C_{N,1} C_{N,2} \ldots C_{N,N}

出力

条件を満たすA,B の組が存在しない場合

一行目にNo と出力せよ。

No

条件を満たすA,B の組が存在する場合

一行目に Yes と出力せよ。二行目には各要素を空白で区切って数列 A を出力せよ。三行目には各要素を空白で区切って数列 B を出力せよ。

条件を満たす解が複数存在する場合は、どれを出力してもよい。

Yes
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

入力例 1

出力例 1

Yes
2 0 1
2 1 3

A,B は非負整数列であることに注意してください。

入力例 2

出力例 2

No

Score : 400 points

Problem Statement

Given is an N \times N matrix C whose elements are non-negative integers. Determine whether there is a pair of sequences of non-negative integers A_1,A_2,\ldots,A_N and B_1,B_2,\ldots,B_N such that C_{i,j}=A_i+B_j for every (i, j). If the answer is yes, print one such pair.

Constraints

1 \leq N \leq 500
0 \leq C_{i,j} \leq 10^9

Input

Input is given from Standard Input in the following format:

N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
:
C_{N,1} C_{N,2} \ldots C_{N,N}

Output

If no pair A, B satisfies the condition:

Print No in the first line.

No

If some pair A, B satisfies the condition:

In the first line, print Yes. In the second line, print the elements of A, with spaces in between. In the third line, print the elements of B, with spaces in between.

If multiple pairs satisfy the condition, any of them will be accepted.

Yes
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Sample Input 1

Sample Output 1

Yes
2 0 1
2 1 3

Note that A and B consist of non-negative integers.

Sample Input 2

Sample Output 2

No

C - ℕ Coloring

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N が与えられます。以下の条件を満たす長さ N の正の整数の列 A_1,A_2,\ldots,A_N であって、数列に現れる値の最大値が最小になるものを一つ出力してください。

i が j の約数ならば、A_i \neq A_j (1 \leq i < j \leq N)

制約

1 \leq N \leq 10^5

入力

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

出力

数列の各要素を空白で区切って一行に出力せよ。

条件を満たす解が複数存在する場合は、どれを出力してもよい。

A_1 A_2 \ldots A_N

入力例 1

出力例 1

1 2 2 3

この出力は以下の条件をすべて満たします。

A_1 \neq A_2
A_1 \neq A_3
A_1 \neq A_4
A_2 \neq A_4

また、登場する値の最大値が 2 以下である数列であって、これらの条件をすべて満たすものは存在しないので、この出力は適当です。

Score : 500 points

Problem Statement

Given is an integer N. Among the sequences of N positive integers A_1, A_2, \ldots, A_N satisfying the following condition, print one that minimizes the maximum value in the sequence.

If i divides j, A_i \neq A_j (1 \leq i < j \leq N).

Constraints

1 \leq N \leq 10^5

Input

Input is given from Standard Input in the following format:

Output

Print a line containing the elements of your sequence, with spaces in between.

If there are multiple valid solutions, any of them will be accepted.

A_1 A_2 \ldots A_N

Sample Input 1

Sample Output 1

1 2 2 3

This solution satisfies all of the following conditions:

A_1 \neq A_2
A_1 \neq A_3
A_1 \neq A_4
A_2 \neq A_4

Additionally, there is no sequence satisfying these conditions where the maximum value in the sequence is 2 or less, so this is a valid solution.

D - Odd Degree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, \ldots, N の番号がついています。i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。このグラフの全域部分グラフ(※)であって、次数が奇数の頂点がちょうど K 個であるものの個数をすべての K(0 \leq K \leq N) について求めてください。ただし答えは非常に大きくなる可能性があるので、998244353 で割った余りを出力してください。

(※)G の部分グラフ H が G の全域部分グラフであるとは、H の頂点集合が G の頂点集合と等しく、H の辺集合が G の辺集合の部分集合であることをいいます。

制約

1 \leq N \leq 5000
0 \leq M \leq 5000
1 \leq A_i , B_i \leq N
与えられるグラフは単純グラフである。すなわち、自己ループや多重辺は存在しない。

入力

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

N M
A_1 B_1
A_2 B_2
:
A_M B_M

出力

N+1 行出力せよ。i 行目には、K=i-1 のときの答えを出力せよ。

ans_0
ans_1
:
ans_N

入力例 1

3 2
1 2
2 3

出力例 1

各全域部分グラフの次数が奇数の頂点の個数は以下の通りです。

辺が無いとき、次数が奇数の頂点は 0 個
1 と 2 を結ぶ辺だけがあるとき、次数が奇数の頂点は 2 個
2 と 3 を結ぶ辺だけがあるとき、次数が奇数の頂点は 2 個
両方の辺があるとき、次数が奇数の頂点は 2 個

入力例 2

4 2
1 2
3 4

出力例 2

Score : 600 points

Problem Statement

Given is a simple undirected graph with N vertices and M edges, where the vertices are numbered 1, \ldots, N and the i-th edge connects Vertex A_i and Vertex B_i. For each K(0 \leq K \leq N), find the number of spanning subgraphs (※) with exactly K vertices with odd degrees. Since the answers can be enormous, print it modulo 998244353.

(※) A subgraph H of G is said to be a spanning subgraph of G when the vertex set of H equals the vertex set of G and the edge set of H is a subset of the edge set of G.

Constraints

1 \leq N \leq 5000
0 \leq M \leq 5000
1 \leq A_i , B_i \leq N
The given graph is simple, that is, it contains no self-loops and no multi-edges.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Print N+1 lines. The i-th line should contain the answer for K=i-1.

ans_0
ans_1
:
ans_N

Sample Input 1

3 2
1 2
2 3

Sample Output 1

Each spanning subgraph has the following number of vertices with odd degrees:

the subgraph with no edges has 0 vertices with odd degrees;
the subgraph with just the edge connecting 1 and 2 has 2 vertices with odd degrees;
the subgraph with just the edge connecting 2 and 3 has 2 vertices with odd degrees;
the subgraph with both edges has 2 vertices with odd degrees.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

E - LEQ and NEQ

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A_1,A_2,\ldots,A_N が与えられます。長さ N の整数列 X_1,X_2,\ldots,X_N であって、以下の条件をすべて満たすものはいくつあるか求め、998244353 で割った余りを出力してください。

1 \leq X_i \leq A_i
X_i \neq X_{i+1} (1 \leq i \leq N-1)

制約

2 \leq N \leq 5 \times 10^5
1 \leq A_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 2

出力例 1

条件をすべて満たす整数列は以下の 6 通りです。

1,2,1
1,3,1
1,3,2
2,1,2
2,3,1
2,3,2

入力例 2

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

出力例 2

524691026

Score : 700 points

Problem Statement

Given is a sequence of N integers A_1,A_2,\ldots,A_N. Print the number, modulo 998244353, of sequences of N integers X_1,X_2,\ldots,X_N satisfying all of the following conditions:

1 \leq X_i \leq A_i
X_i \neq X_{i+1} (1 \leq i \leq N-1)

Constraints

2 \leq N \leq 5 \times 10^5
1 \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
2 3 2

Sample Output 1

The following six sequences satisfy all of the conditions.

1,2,1
1,3,1
1,3,2
2,1,2
2,3,1
2,3,2

Sample Input 2

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

Sample Output 2

524691026

F - Migration

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 頂点の木が与えられます。頂点には 1, \ldots,N の番号がついており、i 番目の辺は頂点 u_i と頂点 v_i をつないでいます。また、頂点 i には整数 h_i が書かれています。
駒が K 個あり、i 番目の駒ははじめ頂点 s_i に置かれています。あなたはこれから「一つ駒を選び、それが現在置かれている頂点に隣接するいずれかの頂点に移動させる」という操作を繰り返します。各駒 i が頂点 t_i に置かれている状態になったら操作を終了します。各駒 i を頂点 s_i から頂点 t_i へ最短経路で移動させる必要はありません。
ある駒の配置に対して、それぞれの駒が置かれている頂点に書かれた整数を足し合わせた値をポテンシャルと呼ぶことにします。ただし、同じ頂点に複数の駒がある場合、その頂点の整数はその駒の個数だけ足し合わせるものとします。
操作を通してのポテンシャルの最大値は最小でいくつになるか求めてください。ただし、はじめの状態と終わりの状態も考えるものとします。

制約

1 \leq N,K \leq 2000
1 \leq u_i,v_i \leq N
1 \leq h_i \leq 10^9
1 \leq s_i,t_i \leq N
与えられるグラフは木

入力

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

N
h_1 h_2 \ldots h_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
K
s_1 t_1
s_2 t_2
:
s_K t_K

出力

答えを出力せよ。

入力例 1

出力例 1

以下のように操作をすることで操作を通してのポテンシャルの最大値は 4 となります。

はじめ、ポテンシャルは 3。
駒 2 を頂点 2 に移動させる。ポテンシャルは 4 になる。
駒 2 を頂点 1 に移動させる。ポテンシャルは 2 になる。
駒 1 を頂点 2 に移動させる。ポテンシャルは 4 になる。
駒 1 を頂点 3 に移動させる。ポテンシャルは 3 になる。

ポテンシャルの最大値が 4 より小さくなるような操作の方法は存在しないため、4 が答えです。

入力例 2

7
100 101 1 100 101 1 1000
1 2
2 3
4 5
5 6
1 7
4 7
2
1 3
4 6

出力例 2

入力例 3

5
2 1 100 5 6
1 2
2 3
3 4
3 5
2
2 2
4 5

出力例 3

入力例 4

出力例 4

入力例 5

6
1 100 1 1 10 1000
1 2
2 3
4 5
1 6
4 6
3
1 3
5 5
5 5

出力例 5

Score : 1000 points

Problem Statement

Given is a tree with N vertices numbered 1, \ldots, N. The i-th edge connects Vertex u_i and Vertex v_i. Additionally, Vertex i has an integer h_i written on it.
We have K pieces, the i-th of which is initially on Vertex s_i. You will repeat the following operation: choose a piece and move it to one of the vertices adjacent to the vertex the piece is currently on. You will end this process when each piece i is on Vertex t_i. It is not required for each piece i to go along the shortest path from Vertex s_i to Vertex t_i.
For an arrangement of the pieces, let its potential be the sum of the integers written on the vertices the pieces are on. If multiple pieces are on the same vertex, the integer on that vertex is added the number of times equal to that number of pieces.
Find the minimum possible value of the maximum potential during the process, including the initial and final states.

Constraints

1 \leq N,K \leq 2000
1 \leq u_i,v_i \leq N
1 \leq h_i \leq 10^9
1 \leq s_i,t_i \leq N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 \ldots h_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
K
s_1 t_1
s_2 t_2
:
s_K t_K

Output

Print the answer.

Sample Input 1

Sample Output 1

We can make 4 the maximum potential during the process, as follows:

Initially, the potential is 3.
Move Piece 2 to Vertex 2. The potential is now 4.
Move Piece 2 to Vertex 1. The potential is now 2.
Move Piece 1 to Vertex 2. The potential is now 4.
Move Piece 1 to Vertex 3. The potential is now 3.

There is no way to make the maximum potential during the process less than 4, so the answer is 4.

Sample Input 2

7
100 101 1 100 101 1 1000
1 2
2 3
4 5
5 6
1 7
4 7
2
1 3
4 6

Sample Output 2

Sample Input 3

5
2 1 100 5 6
1 2
2 3
3 4
3 5
2
2 2
4 5

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

6
1 100 1 1 10 1000
1 2
2 3
4 5
1 6
4 6
3
1 3
5 5
5 5