AtCoder Daily Training HARD 2024/03/28 20:30start

Please sign in first.

E - LRUD Instructions 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面上に高橋君がいます。高橋君は原点から移動を N 回行いました。

N 回の移動は長さ N の文字列で表され、意味は次の通りです。

i 回目の高橋君の移動後の座標は、移動前の座標を (x,y) として、
- S の i 文字目が R であるとき (x+1,y)
- S の i 文字目が L であるとき (x-1,y)
- S の i 文字目が U であるとき (x,y+1)
- S の i 文字目が D であるとき (x,y-1)

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあるかどうかを判定してください。

制約

1 \leq N \leq 2\times 10^5
N は整数
S は R, L, U, D のみからなる長さ N の文字列

入力

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

N
S

出力

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあれば Yes、なければ No と出力せよ。

入力例 1

5
RLURU

出力例 1

Yes

高橋君のいる座標は (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2) と変化します。

入力例 2

20
URDDLLUUURRRDDDDLLLL

出力例 2

No

Score : 300 points

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

Takahashi's coordinates after the i-th move are:
- (x+1,y) if the i-th character of S is R;
- (x-1,y) if the i-th character of S is L;
- (x,y+1) if the i-th character of S is U; and
- (x,y-1) if the i-th character of S is D,
where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

1 \leq N \leq 2\times 10^5
N is an integer.
S is a string of length N consisting of R, L, U, and D.

Input

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

N
S

Output

Print Yes if Takahashi visited the same coordinates multiple times in the course of the N moves; print No otherwise.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

F - Simple path

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

T 上の相異なる 2 頂点 X,Y が与えられるので、頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。

ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。

単純パスとは？

グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y へのパスと呼びます。さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。

制約

1\leq N\leq 2\times 10^5
1\leq X,Y\leq N
X\neq Y
1\leq U_i,V_i\leq N
入力はすべて整数
与えられるグラフは木

入力

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。

入力例 1

出力例 1

2 1 3 5

木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。

入力例 2

出力例 2

1 2

木 T は以下のような形です。

Score : 300 points

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

What is a simple path?

For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.

Constraints

1\leq N\leq 2\times 10^5
1\leq X,Y\leq N
X\neq Y
1\leq U_i,V_i\leq N
All values in the input are integers.
The given graph is a tree.

Input

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.

Sample Input 1

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

Sample Output 2

1 2

The tree T is shown below.

G - Marking

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

0 から N-1 までの番号がつけられた N 個のマスが並んでいます。今から、すぬけくんが以下の手順に従って全てのマスに印をつけていきます。

マス 0 に印をつける。
次の i - iii の手順を N−1 回繰り返す。
1. 最後に印をつけたマスの番号を A としたとき、変数 x を (A+D) \bmod N で初期化する。
2. マス x に印が付いている限り、 x を (x+1) \bmod N に更新することを繰り返す。
3. マス x に印をつける。

すぬけくんが K 番目に印をつけるマスの番号を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1\leq T \leq 10^5
1\leq K\leq N \leq 10^9
1\leq D \leq 10^9
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを意味する。

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

各テストケースは以下の形式で与えられる。

N D K

出力

T 行出力せよ。

i\ (1\leq i \leq T) 行目には、i 番目のテストケースに対する答えを出力せよ。

入力例 1

出力例 1

N=4,D=2 のとき、すぬけくんは以下のように印をつけていきます。

マス 0 に印をつける。
(1回目) x=(0+2)\bmod 4=2 と初期化する。マス 2 は印がついていないので、印をつける。
(2回目) x=(2+2)\bmod 4=0 と初期化する。マス 0 は印がついているので、x=(0+1)\bmod 4=1 と更新する。マス 1 は印がついていないので、印をつける。
(3回目) x=(1+2)\bmod 4=3 と初期化する。マス 3 は印がついていないので、印をつける。

Score : 400 points

Problem Statement

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

Mark square 0.
Repeat the following steps i - iii (N-1) times.
1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
2. While square x is marked, repeat replacing x with (x+1) \bmod N.
3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

1\leq T \leq 10^5
1\leq K\leq N \leq 10^9
1\leq D \leq 10^9
All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N D K

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain the answer to the i-th test case.

Sample Input 1

Sample Output 1

If N=4 and D=2, Snuke marks the squares as follows.

Mark square 0.
(1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
(2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
(3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.

H - Christmas Color Grid 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表記します。

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

1 \leq H,W \leq 1000
S_{i,j} = . または S_{i,j} = #
S_{i,j} = . なる (i,j) が存在する。

入力

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。

入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。

入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean?

It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

1 \leq H,W \leq 1000
S_{i,j} = . or S_{i,j} = #.
There is at least one (i,j) such that S_{i,j} = ..

Input

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

I - Octopus

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

数直線上に 1 体のタコ型ロボットと N 個の宝があります。 i (1\leq i\leq N) 個目の宝はそれぞれ座標 X_i にあります。
タコ型ロボットは 1 つの頭と N 本の足を持っており、i 本目の足の長さは L_i (1\leq i\leq N) です。

タコ型ロボットが次のようにして N 個の宝すべてを掴む事ができるような整数 k の個数を求めてください。

頭を座標 k におく。
i=1,2,\ldots,N の順に、「頭から距離 L_i 以下の範囲、すなわち k-L_i\leq x\leq k+L_i をみたす座標 x にまだ掴んでいない宝が存在する場合、そのうちの 1 つを選んで掴む」ことを繰り返す。

制約

1 \leq N\leq 200
-10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
入力はすべて整数

入力

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

N
X_1 X_2 \ldots X_N
L_1 L_2 \ldots L_N

出力

問題文の条件をみたす整数 k の個数を出力せよ。

入力例 1

3
-6 0 7
3 5 10

出力例 1

k=-3,-2,-1,2,3,4 が条件をみたします。例えば、k=-3 のときは、次のようにして 3 個の宝をすべて掴む事ができます。

1 本目の足は -6\leq x\leq 0 にある宝を掴む事ができる。このうち座標 -6 にある 1 個目の宝を掴む。
2 本目の足は -8\leq x\leq 2 にある宝を掴む事ができる。このうち座標 0 にある 2 個目の宝を掴む。
3 本目の足は -13\leq x\leq 7 にある宝を掴む事ができる。このうち座標 7 にある 3 個目の宝を掴む。

入力例 2

1
0
1000000000000000000

出力例 2

2000000000000000001

-10^{18} 以上 10^{18} 以下のすべての整数が k として条件をみたします。

入力例 3

2
-100 100
1 1

出力例 3

条件をみたす k は存在しません。

Score : 575 points

Problem Statement

There is an octopus-shaped robot and N treasures on a number line. The i-th treasure (1\leq i\leq N) is located at coordinate X_i.
The robot has one head and N legs, and the i-th leg (1\leq i\leq N) has a length of L_i.

Find the number of integers k such that the robot can grab all N treasures as follows.

Place the head at coordinate k.
Repeat the following for i=1,2,\ldots,N in this order: if there is a treasure that has not been grabbed yet within a distance of L_i from the head, that is, at a coordinate x satisfying k-L_i\leq x\leq k+L_i, choose one such treasure and grab it.

Constraints

1 \leq N\leq 200
-10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
All input values are integers.

Input

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

N
X_1 X_2 \ldots X_N
L_1 L_2 \ldots L_N

Output

Print the number of integers k that satisfy the condition in the statement.

Sample Input 1

3
-6 0 7
3 5 10

Sample Output 1

k=-3,-2,-1,2,3,4 satisfy the condition. For example, when k=-3, the robot can grab all three treasures as follows.

The first leg can grab treasures at coordinates x satisfying -6\leq x\leq 0. Among them, grab the first treasure at coordinate -6.
The second leg can grab treasures at coordinates x satisfying -8\leq x\leq 2. Among them, grab the second treasure at coordinate 0.
The third leg can grab treasures at coordinates x satisfying -13\leq x\leq 7. Among them, grab the third treasure at coordinate 7.

Sample Input 2

1
0
1000000000000000000

Sample Output 2

2000000000000000001

All integers k from -10^{18} to 10^{18} satisfy the condition.

Sample Input 3

2
-100 100
1 1

Sample Output 3

No k satisfies the conditions.