E - Make Takahashi Happy

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.

F - Circular Playlist

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
G - Snuke Maze

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
H - Notebook

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
I - Distance Sums 2

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