Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、 上から i 行目、左から j 列目のマス(以下、(i, j) と表す)には、整数 A_{i, j} が書かれています。
いま、高橋君は (1, 1) にいます。 これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。 ただし、その過程でマス目の外部に移動することは出来ません。
その結果、高橋君が通ったマス(始点 (1, 1) と終点 (H, W) を含む)に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。 高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。
制約
- 2 \leq H, W \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
出力
答えを出力せよ。
入力例 1
3 3 3 2 2 2 1 3 1 5 4
出力例 1
3
高橋君の移動経路として考えられるものは下記の 6 通りです。
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
- (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3):通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。
入力例 2
10 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
出力例 2
48620
この例では、高橋君は考えられるどの経路を通っても嬉しくなります。
Score : 300 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.
Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.
Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.
Constraints
- 2 \leq H, W \leq 10
- 1 \leq A_{i, j} \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
Output
Print the answer.
Sample Input 1
3 3 3 2 2 2 1 3 1 5 4
Sample Output 1
3
There are six possible paths:
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
- (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
Thus, the third, fifth, and sixth paths described above make him happy.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Sample Output 2
48620
In this example, every possible path makes him happy.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 曲からなるプレイリストがあり、曲には 1, \dots, N の番号が付けられています。
曲 i の長さは A_i 秒です。
プレイリストを再生すると、曲 1、曲 2、\ldots、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。
プレイリストを再生してから T 秒後に流れているのはどの曲ですか?また、その曲が流れ始めてから何秒の時点ですか?
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。
制約
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 \ldots A_N
出力
プレイリストを再生してから T 秒後に流れている曲の番号と、その曲が流れ始めてから何秒たったかを表す整数を空白区切りで出力せよ。
入力例 1
3 600 180 240 120
出力例 1
1 60
プレイリストを再生してからの様子は次のようになります。
- 0 秒後から 180 秒後まで曲 1 が流れる。
- 180 秒後から 420 秒後まで曲 2 が流れる。
- 420 秒後から 540 秒後まで曲 3 が流れる。
- 540 秒後から 720 秒後まで曲 1 が流れる。
- 720 秒後から 960 秒後まで曲 2 が流れる。
- \qquad\vdots
600 秒後の時点で流れているのは曲 1 であり、流れ始めて 60 秒の時点です。
入力例 2
3 281 94 94 94
出力例 2
3 93
入力例 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
6 678912340
Score : 300 points
Problem Statement
We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.
When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.
At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- The playlist does not change songs at exactly T seconds after it starts playing.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N T A_1 \ldots A_N
Output
Print an integer representing the song that is playing at exactly T seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.
Sample Input 1
3 600 180 240 120
Sample Output 1
1 60
When the playlist is played, the following happens. (Assume that it starts playing at time 0.)
- From time 0 to time 180, song 1 plays.
- From time 180 to time 420, song 2 plays.
- From time 420 to time 540, song 3 plays.
- From time 540 to time 720, song 1 plays.
- From time 720 to time 960, song 2 plays.
- \qquad\vdots
At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.
Sample Input 2
3 281 94 94 94
Sample Output 2
3 93
Sample Input 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
6 678912340
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
H 行 W 列のグリッドがあります。 以下、上から i 行目、左から j 列目のマスを (i,j) と表記します。 グリッドの各マスには英小文字が書かれており、(i,j) に書かれた文字は与えられる文字列 S_i の j 文字目と一致します。
すぬけくんは、辺で隣接するマスに移動することを繰り返して (1,1) から (H,W) まで移動しようと思っています。
訪れるマス (最初の (1,1) と 最後の (H,W) を含む)に書かれた文字が、
訪れる順に s \rightarrow n \rightarrow u \rightarrow k
\rightarrow e \rightarrow s \rightarrow n \rightarrow \dots
となるような経路が存在するか判定してください。
なお、2 つのマス (i_1,j_1),(i_2,j_2) は |i_1-i_2|+|j_1-j_2| = 1 を満たすとき、またそのときに限り「辺で隣接する」といいます。
より厳密には、マスの列 ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) であって以下の条件を全て満たすものが存在するか判定してください。
- (i_1,j_1) = (1,1),(i_k,j_k) = (H,W)
- すべての t\ (1 \leq t < k) について、(i_t,j_t) と (i_{t+1},j_{t+1}) は辺で隣接する
- すべての t\ (1 \leq t \leq k) について、(i_t,j_t) に書かれた文字は
snukeの ((t-1) \bmod 5) + 1 文字目と一致する
制約
- 2\leq H,W \leq 500
- H,W は整数
- S_i は英小文字からなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
問題文中の条件を満たす経路が存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
2 3 sns euk
出力例 1
Yes
(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) という経路は、訪れたマスに書かれた文字が訪れた順に
s \rightarrow n \rightarrow u \rightarrow k となるため条件を満たします。
入力例 2
2 2 ab cd
出力例 2
No
入力例 3
5 7 skunsek nukesnu ukeseku nsnnesn uekukku
出力例 3
Yes
Score : 400 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.
Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W).
Determine if there is a path
in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are
s \rightarrow n \rightarrow u \rightarrow k
\rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting.
Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.
Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:
- (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
- (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
- the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of
snuke, for all t\ (1 \leq t \leq k).
Constraints
- 2\leq H,W \leq 500
- H and W are integers.
- S_i is a string of length W consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print Yes if there is a path satisfying the conditions in the problem statement; print No otherwise.
Sample Input 1
2 3 sns euk
Sample Output 1
Yes
The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions
because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.
Sample Input 2
2 2 ab cd
Sample Output 2
No
Sample Input 3
5 7 skunsek nukesnu ukeseku nsnnesn uekukku
Sample Output 3
Yes
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
整数列 A とノートがあります。ノートには 10^9 枚のページがあります。
Q 個のクエリが与えられます。各クエリは下記の 4 種類のいずれかです。
ADD x : 整数 x を A の末尾に追加する。
DELETE : A の末尾の要素を削除する。ただし、A が空である場合は何もしない。
SAVE y : ノートの y ページ目に書かれている数列を消し、代わりに現在の A を y ページ目に書き込む。
LOAD z : A をノートの z ページ目に書かれている数列で置き換える。
はじめ、A は空列であり、ノートのすべてのページには空列の情報が書かれています。 その初期状態から、Q 個のクエリを与えられる順に実行し、各クエリの実行直後における A の末尾の要素を出力してください。
なお、入出力の量が多くなる場合があるので、高速な方法で入出力を行うことを推奨します。
制約
- 1 \leq Q \leq 5 \times 10^5
- 1 \leq x, y, z \leq 10^9
- Q, x, y, z は整数
- 与えられるクエリは問題文中の 4 種類のいずれか
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
出力
下記の形式にしたがい、i = 1, 2, \ldots, Q について、i 番目までのクエリを実行した直後の A の末尾の要素 X_i を( A が空の場合は X_i := -1 とする)出力せよ。
X_1 X_2 \ldots X_Q
入力例 1
11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1
出力例 1
3 3 4 4 3 -1 -1 4 4 -1 4
はじめ、A は空列、すなわち A = () であり、ノートのすべてのページには空列の情報が書かれています。
- 1 番目のクエリによって、 A の末尾に 3 が追加され、A = (3) となります。
- 2 番目のクエリによって、ノートの 1 ページ目に書かれた数列が (3) になります。A は変わらず A = (3) です。
- 3 番目のクエリによって、 A の末尾に 4 が追加され、A = (3, 4) となります。
- 4 番目のクエリによって、ノートの 2 ページ目に書かれた数列が (3, 4) になります。A は変わらず A = (3, 4) です。
- 5 番目のクエリによって、 A がノートの 1 ページ目に書かれた数列 (3) で置き換えられ、A = (3) となります。
- 6 番目のクエリによって、 A の末尾の要素が削除され、A = () となります。
- 7 番目のクエリでは、A がすでに空であるので何もしません。A は変わらず A = () です。
- 8 番目のクエリによって、 A がノートの 2 ページ目に書かれた数列 (3, 4) で置き換えられ、A = (3, 4) となります。
- 9 番目のクエリによって、ノートの 1 ページ目に書かれた数列が (3, 4) になります。A は変わらず A = (3, 4) です。
- 10 番目のクエリによって、 A がノートの 3 ページ目に書かれた数列 () で置き換えられ、A = () となります。
- 11 番目のクエリによって、 A がノートの 1 ページ目に書かれた数列 (3, 4) で置き換えられ、A = (3, 4) となります。
入力例 2
21 ADD 4 ADD 3 DELETE ADD 10 LOAD 7 SAVE 5 SAVE 5 ADD 4 ADD 4 ADD 5 SAVE 5 ADD 2 DELETE ADD 1 SAVE 5 ADD 7 ADD 8 DELETE ADD 4 DELETE LOAD 5
出力例 2
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1
Score : 500 points
Problem Statement
We have an integer sequence A and a notebook. The notebook has 10^9 pages.
You are given Q queries. Each query is of one of the following four kinds:
ADD x: append an integer x to the tail of A.
DELETE: remove the last term of A if A is not empty; do nothing otherwise.
SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.
LOAD z: replace A with the sequence recorded on the z-th page of the notebook.
Initially, A is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process Q queries successively in the given order and print the last term of A after processing each query.
The use of fast input and output methods is recommended because of potentially large input and output.
Constraints
- 1 \leq Q \leq 5 \times 10^5
- 1 \leq x, y, z \leq 10^9
- Q, x, y, and z are integers.
- Each of the given queries is of one of the four kinds in the Problem Statement.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Output
For each i = 1, 2, \ldots, Q, let X_i be the last element of A after processing up to the i-th query, or let X_i := -1 if A is empty, and print them in the following format:
X_1 X_2 \ldots X_Q
Sample Input 1
11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1
Sample Output 1
3 3 4 4 3 -1 -1 4 4 -1 4
Initially, A is an empty sequence, so A = (), and an empty sequence is recorded on each page of the notebook.
- By the 1-st query, 3 is appended to the tail of A, resulting in A = (3).
- By the 2-nd query, the sequence recorded on the 1-st page of the notebook becomes (3). It remains that A = (3).
- By the 3-rd query, 4 is appended to the tail of A, resulting in A = (3, 4).
- By the 4-th query, the sequence recorded on the 2-nd page of the notebook becomes (3, 4). It remains that A = (3, 4).
- By the 5-th query, A is replaced by (3), which is recorded on the 1-st page of the notebook, resulting in A = (3).
- By the 6-th query, the last term of A is removed, resulting in A = ().
- By the 7-th query, nothing happens because A is already empty. It remains that A = ().
- By the 8-th query, A is replaced by (3,4), which is recorded on the 2-nd page of the notebook, resulting in A = (3, 4).
- By the 9-th query, the sequence recorded on the 1-st page of the notebook becomes (3, 4). It remains that A = (3, 4).
- By the 10-th query, A is replaced by (), which is recorded on the 3-rd page of the notebook, resulting in A = ().
- By the 11-th query, A is replaced by (3, 4), which is recorded on the 1-st page of the notebook, resulting in A = (3, 4).
Sample Input 2
21 ADD 4 ADD 3 DELETE ADD 10 LOAD 7 SAVE 5 SAVE 5 ADD 4 ADD 4 ADD 5 SAVE 5 ADD 2 DELETE ADD 1 SAVE 5 ADD 7 ADD 8 DELETE ADD 4 DELETE LOAD 5
Sample Output 2
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 頂点の木が与えられます。頂点には 1,2,\ldots ,N の番号がついており、i 番目の辺は頂点 u_i,v_i を結ぶ無向辺です。
各整数 i\,(1 \leq i \leq N) に対して、\sum_{j=1}^{N}dis(i,j) を求めてください。
ただし、dis(i,j) は頂点 i から頂点 j に到達する際にたどる必要のある最小の辺数です。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
N 行出力せよ。
i 行目には \sum_{j=1}^{N}dis(i,j) を出力せよ。
入力例 1
3 1 2 2 3
出力例 1
3 2 3
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3、
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2、
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3、
です。
入力例 2
2 1 2
出力例 2
1 1
入力例 3
6 1 6 1 5 1 3 1 4 1 2
出力例 3
5 9 9 9 9 9
Score : 500 points
Problem Statement
Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.
For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).
Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
Output
Print N lines.
The i-th line should contain \sum_{j=1}^{N}dis(i,j).
Sample Input 1
3 1 2 2 3
Sample Output 1
3 2 3
We have:
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.
Sample Input 2
2 1 2
Sample Output 2
1 1
Sample Input 3
6 1 6 1 5 1 3 1 4 1 2
Sample Output 3
5 9 9 9 9 9