AtCoder Daily Training MEDIUM 2024/05/23 20:30start

C - Adjacency Matrix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。

G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。

i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。

ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。

制約

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
入力される値はすべて整数

入力

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

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

出力

N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。

入力例 1

出力例 1

頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。

同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。

入力例 2

2
0 0
0 0

出力例 2

G に辺が存在しないこともあります。

入力例 3

出力例 3

Score: 150 points

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
All input values are integers.

Input

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

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

Output

Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.

Sample Input 1

Sample Output 1

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

Sample Output 3

D - Strictly Superior

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 商店には N 個の商品があります。 i\ (1\leq i\leq N) 番目の商品の価格は P _ i です。 i\ (1\leq i\leq N) 番目の商品は C _ i 個の機能をもち、i\ (1\leq i\leq N) 番目の商品の j\ (1\leq j\leq C _ i) 番目の機能は 1 以上 M 以下の整数 F _ {i,j} として表されます。

高橋くんは、AtCoder 商店の商品で一方が一方の上位互換であるものがないか気になりました。 i 番目の商品と j 番目の商品 (1\leq i,j\leq N) であって、次の条件をすべて満たすものがあるとき Yes と、ないとき No と出力してください。

P _ i\geq P _ j である。
j 番目の製品は i 番目の製品がもつ機能をすべてもつ。
P _ i\gt P _ j であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ。

制約

2\leq N\leq100
1\leq M\leq100
1\leq P _ i\leq10^5\ (1\leq i\leq N)
1\leq C _ i\leq M\ (1\leq i\leq N)
1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
入力はすべて整数

入力

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

出力

答えを 1 行で出力せよ。

入力例 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

出力例 1

Yes

(i,j)=(4,3) とすると、条件を全て満たします。

他の組は条件を満たしません。例えば (i,j)=(4,5) とすると j 番目の商品は i 番目の商品の機能をすべてもっていますが、P _ i\lt P _ j なので上位互換ではありません。

入力例 2

出力例 2

No

まったく同じ価格と機能をもった商品がある場合もあります。

入力例 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

出力例 3

Yes

Score : 200 points

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

P _ i\geq P _ j.
The j-th product has all functions of the i-th product.
P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

2\leq N\leq100
1\leq M\leq100
1\leq P _ i\leq10^5\ (1\leq i\leq N)
1\leq C _ i\leq M\ (1\leq i\leq N)
1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
All input values are integers.

Input

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

Output

Print the answer in a single line.

Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.

Sample Input 2

Sample Output 2

No

Multiple products may have the same price and functions.

Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes

E - Sum of Numbers Greater Than Me

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

i=1,\ldots,N のそれぞれについて次の問題を解いてください。

問題：A の要素のうち A_i より大きな要素全ての和を求めよ。

制約

1 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

各 1\leq k\leq N について、i=k に対する問題の答えを B_k とする。B_1,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

5
1 4 1 4 2

出力例 1

10 0 10 0 8

i=1 のとき A_1=1 より大きな要素の和は 4+4+2=10
i=2 のとき A_2=4 より大きな要素の和は 0
i=3 のとき A_3=1 より大きな要素の和は 4+4+2=10
i=4 のとき A_4=4 より大きな要素の和は 0
i=5 のとき A_5=2 より大きな要素の和は 4+4=8

入力例 2

10
31 42 59 26 53 58 97 93 23 54

出力例 2

456 414 190 487 361 249 0 97 513 307

入力例 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

1 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

For each 1\leq k\leq N, let B_k be the answer to the problem when i=k. Print B_1,\ldots,B_N in this order, separated by spaces.

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
For i=2, the sum of elements greater than A_2=4 is 0.
For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
For i=4, the sum of elements greater than A_4=4 is 0.
For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

F - Slot Strategy

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。ここで、S_i は 0, 1, \ldots, 9 がちょうど 1 回ずつ現れる長さ 10 の文字列です。

それぞれのリールには対応するボタンがついており、高橋君は各非負整数 t について、スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す（または何もしない）ことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、 i 番目のリールは S_i の (t\bmod{10})+1 文字目を表示して止まります。
ただし、t\bmod{10} で t を 10 で割ったあまりを表します。

高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。

制約

2\leq N\leq 100
N は整数
S_i は 0, 1, \ldots, 9 がちょうど 1 回ずつ現れる長さ 10 の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを出力せよ。

入力例 1

出力例 1

高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 6 秒後にリールに表示される文字を 8 で揃えることができます。

スロットの回転開始から 0 秒後に 2 番目のリールに対応するボタンを押します。2 番目のリールは S_2 の (0\bmod{10})+1=1 文字目である 8 を表示して止まります。
スロットの回転開始から 2 秒後に 3 番目のリールに対応するボタンを押します。3 番目のリールは S_3 の (2\bmod{10})+1=3 文字目である 8 を表示して止まります。
スロットの回転開始から 6 秒後に 1 番目のリールに対応するボタンを押します。1 番目のリールは S_1 の (6\bmod{10})+1=7 文字目である 8 を表示して止まります。

5 秒以下で全てのリールに表示されている文字を揃える方法はないため、6 を出力します。

入力例 2

出力例 2

全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。

Score : 300 points

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

2\leq N\leq 100
N is an integer.
S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print the minimum number of seconds needed to achieve Takahashi's objective after the start of the spin.

Sample Input 1

Sample Output 1

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

Sample Output 2

Note that he must stop all reels to make them display the same character.

G - Iroha and Haiku (New ABC Edition)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の数列 A=(A_0,\ldots,A_{N-1}) があります。
次の条件を全て満たす整数の組 (x,y,z,w) が存在するか判定してください。

0 \leq x < y < z < w \leq N
A_x + A_{x+1} + \ldots + A_{y-1} = P
A_y + A_{y+1} + \ldots + A_{z-1} = Q
A_z + A_{z+1} + \ldots + A_{w-1} = R

制約

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq P,Q,R \leq 10^{15}
入力に含まれる値は全て整数である

入力

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

N P Q R
A_0 A_1 \ldots A_{N-1}

出力

条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。

入力例 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

出力例 1

Yes

(x,y,z,w)=(1,3,6,8) が条件を満たします。

入力例 2

9 100 101 100
31 41 59 26 53 58 97 93 23

出力例 2

No

入力例 3

7 1 1 1
1 1 1 1 1 1 1

出力例 3

Yes

Score : 400 points

Problem Statement

There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:

0 \leq x < y < z < w \leq N
A_x + A_{x+1} + \ldots + A_{y-1} = P
A_y + A_{y+1} + \ldots + A_{z-1} = Q
A_z + A_{z+1} + \ldots + A_{w-1} = R

Constraints

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq P,Q,R \leq 10^{15}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P Q R
A_0 A_1 \ldots A_{N-1}

Output

If there exists a tuple that satisfies the conditions, print Yes; otherwise, print No.

Sample Input 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

Sample Output 1

Yes

(x,y,z,w)=(1,3,6,8) satisfies the conditions.

Sample Input 2

9 100 101 100
31 41 59 26 53 58 97 93 23

Sample Output 2

No

Sample Input 3

7 1 1 1
1 1 1 1 1 1 1

Sample Output 3

Yes