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
3 1937458062 8124690357 2385760149
出力例 1
6
高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 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
5 0123456789 0123456789 0123456789 0123456789 0123456789
出力例 2
40
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
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,9exactly 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
3 1937458062 8124690357 2385760149
Sample Output 1
6
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
5 0123456789 0123456789 0123456789 0123456789 0123456789
Sample Output 2
40
Note that he must stop all reels to make them display the same character.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます。
以下の条件を満たす長さ N の整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するならば一つ出力してください。
- 各 i=1,2,\ldots,N に対して L_i\leq X_i\leq R_i
- \displaystyle \sum_{i=1}^N X_i=0
制約
- 1\leq N\leq 2\times 10^5
- -10^9\leq L_i\leq R_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
存在しない場合は No を出力せよ。存在する場合は条件を満たす整数列 X を以下の形式で出力せよ。
Yes X_1 X_2 \ldots X_N
答えが複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 3 5 -4 1 -2 3
出力例 1
Yes 4 -3 -1
数列 X=(4,-3,-1) は問題の条件をすべて満たします。ほかにも (3,-3,0) や (5,-4,-1) などが条件を満たします。
入力例 2
3 1 2 1 2 1 2
出力例 2
No
条件を満たす整数列 X は存在しません。
入力例 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
出力例 3
Yes -66 -57 31 -6 89 9
Score : 350 points
Problem Statement
You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).
Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.
- L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
- \displaystyle \sum_{i=1}^N X_i = 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq L_i \leq R_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
If no solution exists, print No. Otherwise, print an integer sequence X that satisfies the conditions in the following format:
Yes X_1 X_2 \ldots X_N
If multiple solutions exist, any of them will be considered correct.
Sample Input 1
3 3 5 -4 1 -2 3
Sample Output 1
Yes 4 -3 -1
The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).
Sample Input 2
3 1 2 1 2 1 2
Sample Output 2
No
No sequence X satisfies the conditions.
Sample Input 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
Sample Output 3
Yes -66 -57 31 -6 89 9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N \times N のマス目が与えられます。このうち上から i 行目、左から j 列目のマスを (i,j) と書きます。
各マスの状態を表す N 個の長さ N の文字列 S_1,S_2,\dots,S_N が以下の形式で与えられます。
- S_i の j 文字目が
oであるとき、 (i,j) にはoが書かれている。 - S_i の j 文字目が
xであるとき、 (i,j) にはxが書かれている。
以下の条件を全て満たすマスの三つ組の個数を求めてください。
- 組に含まれる 3 マスは相異なる。
- 3 マス全てに
oが書かれている。 - マスのうち、丁度 2 つが同じ行にある。
- マスのうち、丁度 2 つが同じ列にある。
但し、ふたつの三つ組は、丁度一方に含まれるマスが存在する場合のみ区別します。
制約
- N は 2 以上 2000 以下の整数
- S_i は長さ N の
oとxからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
3 ooo oxx xxo
出力例 1
4
以下の 4 つの三つ組が条件を満たします。
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
入力例 2
4 oxxx xoxx xxox xxxo
出力例 2
0
入力例 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
出力例 3
2960
Score : 400 points
Problem Statement
You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:
- If the j-th character of S_i is
o, there is anowritten in cell (i,j). - If the j-th character of S_i is
x, there is anxwritten in cell (i,j).
Find the number of triples of cells that satisfy all of the following conditions:
- The three cells in the triple are distinct.
- All three cells have an
owritten in them. - Exactly two of the cells are in the same row.
- Exactly two of the cells are in the same column.
Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.
Constraints
- N is an integer between 2 and 2000, inclusive.
- S_i is a string of length N consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
3 ooo oxx xxo
Sample Output 1
4
The following four triples satisfy the conditions:
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
Sample Input 2
4 oxxx xoxx xxox xxxo
Sample Output 2
0
Sample Input 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
Sample Output 3
2960
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) と、正整数 M が与えられます。
次の値を求めてください。
\[ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) \]
ここで、X \mathbin{\mathrm{mod}} M で、非負整数 X を M で割ったあまりを表します。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 4 2 5 0
出力例 1
10
- A_1 \mathbin{\mathrm{mod}} M = 2
- (A_1+A_2) \mathbin{\mathrm{mod}} M = 3
- (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3
- A_2 \mathbin{\mathrm{mod}} M = 1
- (A_2+A_3) \mathbin{\mathrm{mod}} M = 1
- A_3 \mathbin{\mathrm{mod}} M = 0
これらの総和の 10 が答えです。外側の総和のあまりは取らないことに注意してください。
入力例 2
10 100 320 578 244 604 145 839 156 857 556 400
出力例 2
2736
Score : 475 points
Problem Statement
You are given a sequence A = (A_1, A_2, \dots, A_N) of N non-negative integers, and a positive integer M.
Find the following value:
\[ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right). \]
Here, X \mathbin{\mathrm{mod}} M denotes the remainder when the non-negative integer X is divided by M.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 4 2 5 0
Sample Output 1
10
- A_1 \mathbin{\mathrm{mod}} M = 2
- (A_1+A_2) \mathbin{\mathrm{mod}} M = 3
- (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3
- A_2 \mathbin{\mathrm{mod}} M = 1
- (A_2+A_3) \mathbin{\mathrm{mod}} M = 1
- A_3 \mathbin{\mathrm{mod}} M = 0
The answer is the sum of these values, 10. Note that the outer sum is not taken modulo M.
Sample Input 2
10 100 320 578 244 604 145 839 156 857 556 400
Sample Output 2
2736
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 頂点の木があります。 1 番目の頂点が根であり、i 番目 (2\leq i\leq N) の頂点の親は p _ i\ (1\leq p _ i\lt i) です。
根でない頂点には、敵か薬のどちらか一方が配置されています。 高橋くんは、すべての敵を倒したいです。 はじめ、高橋くんの強さは 1 で、頂点 1 にいます。 i=2,\ldots,N について、i 番目の頂点の情報は整数の組 (t _ i,s _ i,g _ i) を用いて次のように表されます。
- t _ i=1 ならば i 番目の頂点には敵がいます。この頂点に高橋くんが初めて訪れたとき、高橋くんの強さが s _ i 未満だった場合高橋くんは敵に倒されて敗北し、高橋くんは他の頂点に移動できなくなります。そうでなかった場合、高橋くんは敵を倒し、強さが g _ i 上昇します。
- t _ i=2 ならば i 番目の頂点には薬があります。この頂点に高橋くんが初めて訪れたとき、高橋くんは薬を飲み、強さが g _ i 倍になります。(薬がある頂点では、s _ i=0 です。)
薬がある頂点はたかだか 10 個です。
高橋くんは、隣接する頂点に移動することができます。 高橋くんがすべての敵を倒すことができるか判定してください。
制約
- 2\leq N\leq 500
- 1\leq p _ i\lt i\ (2\leq i\leq N)
- t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
- t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2\implies s _ i=0\ (2\leq i\leq N)
- 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2 である頂点は 10 個以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N p _ 2 t _ 2 s _ 2 g _ 2 p _ 3 t _ 3 s _ 3 g _ 3 \vdots p _ N t _ N s _ N g _ N
出力
答え(Yes または No)を 1 行で出力せよ。
入力例 1
8 1 2 0 3 2 1 3 3 1 2 0 4 4 1 2 2 1 2 0 5 6 1 5 5 5 1 140 1
出力例 1
Yes
はじめ、木は以下のようになっています。

高橋くんは、頂点 1 から 2,3,2,1,6,7,6,1,4,5,8 の順に移動することで、すべての敵を倒すことができます。 このとき、高橋くんがいる頂点と高橋くんの強さは以下の図のように変化します(図では、すでに訪れたことのある頂点への移動は省略しています)。

例えば、頂点 1 から 4,5,8 の順に移動すると、頂点 8 に訪れた時点での強さが s _ 8=140 より小さいので高橋くんは敗北してしまい、すべての敵を倒すことができません。
入力例 2
12 1 1 166 619 1 1 17 592 2 1 222 983 2 1 729 338 5 1 747 62 3 1 452 815 3 2 0 1 4 2 0 40 4 1 306 520 6 1 317 591 1 1 507 946
出力例 2
No
入力例 3
12 1 1 1 791 2 2 0 410 2 1 724 790 2 1 828 599 5 2 0 13 3 1 550 803 1 1 802 506 5 1 261 587 6 1 663 329 8 1 11 955 9 1 148 917
出力例 3
Yes
入力例 4
12 1 2 0 1000000000 2 2 0 1000000000 3 2 0 1000000000 4 2 0 1000000000 5 2 0 1000000000 6 2 0 1000000000 7 2 0 1000000000 8 2 0 1000000000 9 2 0 1000000000 10 2 0 1000000000 11 1 1 1
出力例 4
Yes
Score : 550 points
Problem Statement
There is a tree with N vertices. The 1-st vertex is the root, and the parent of the i-th vertex (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).
Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is 1, and he is at vertex 1. For i=2,\ldots,N, the information of the i-th vertex is represented by a triple of integers (t _ i,s _ i,g _ i) as follows.
- If t _ i=1, there is an enemy at the i-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than s _ i, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by g _ i.
- If t _ i=2, there is a medicine at the i-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by g _ i. (For a vertex with a medicine, s _ i=0.)
There are at most 10 vertices with a medicine.
Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.
Constraints
- 2\leq N\leq 500
- 1\leq p _ i\lt i\ (2\leq i\leq N)
- t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
- t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
- t _ i=2\implies s _ i=0\ (2\leq i\leq N)
- 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
- There are at most 10 vertices with t _ i=2.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N p _ 2 t _ 2 s _ 2 g _ 2 p _ 3 t _ 3 s _ 3 g _ 3 \vdots p _ N t _ N s _ N g _ N
Output
Print the answer (Yes or No) in one line.
Sample Input 1
8 1 2 0 3 2 1 3 3 1 2 0 4 4 1 2 2 1 2 0 5 6 1 5 5 5 1 140 1
Sample Output 1
Yes
Initially, the tree looks like this:

Takahashi can defeat all the enemies by moving from vertex 1 to 2,3,2,1,6,7,6,1,4,5,8 in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).

On the other hand, if he moves from vertex 1 to 4,5,8 in this order, for example, his strength when visiting vertex 8 will be less than s _ 8=140, so he will lose without defeating all the enemies.
Sample Input 2
12 1 1 166 619 1 1 17 592 2 1 222 983 2 1 729 338 5 1 747 62 3 1 452 815 3 2 0 1 4 2 0 40 4 1 306 520 6 1 317 591 1 1 507 946
Sample Output 2
No
Sample Input 3
12 1 1 1 791 2 2 0 410 2 1 724 790 2 1 828 599 5 2 0 13 3 1 550 803 1 1 802 506 5 1 261 587 6 1 663 329 8 1 11 955 9 1 148 917
Sample Output 3
Yes
Sample Input 4
12 1 2 0 1000000000 2 2 0 1000000000 3 2 0 1000000000 4 2 0 1000000000 5 2 0 1000000000 6 2 0 1000000000 7 2 0 1000000000 8 2 0 1000000000 9 2 0 1000000000 10 2 0 1000000000 11 1 1 1
Sample Output 4
Yes