AtCoder Daily Training MEDIUM 2025/10/09 18:30start

C - Grid Walk

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

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

マス (i, j) は C_{i, j} が . のとき空きマスであり、# のとき空きマスではありません。

高橋君は現在マス (S_i, S_j) におり、i = 1, 2, \ldots, |X| の順に以下のルールに従って行動します。

X の i 文字目が L のとき、高橋君が現在いるマスの 1 つ左のマスが存在し、そのマスが空きマスならば 1 つ左のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が R のとき、高橋君が現在いるマスの 1 つ右のマスが存在し、そのマスが空きマスならば 1 つ右のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が U のとき、高橋君が現在いるマスの 1 つ上のマスが存在し、そのマスが空きマスならば 1 つ上のマスに移動する。そうでないならば、現在いるマスに留まる。
X の i 文字目が D のとき、高橋君が現在いるマスの 1 つ下のマスが存在し、そのマスが空きマスならば 1 つ下のマスに移動する。そうでないならば、現在いるマスに留まる。

一連の行動を終えた後高橋君がどのマスにいるか出力してください。

制約

1 \leq H, W \leq 50
1 \leq S_i \leq H
1 \leq S_j \leq W
H, W, S_i, S_j は整数
C_{i, j} は . または #
C_{S_i, S_j} = .
X は L, R, U, D からなる長さ 1 以上 50 以下の文字列

入力

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

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

出力

高橋君が一連の行動を終えた後にいるマスをマス (x, y) として、x と y をこの順に空白区切りで出力せよ。

入力例 1

2 3
2 1
.#.
...
ULDRU

出力例 1

2 2

高橋君ははじめマス (2, 1) にいます。高橋君の一連の行動は以下のようになります。

X の 1 文字目は U であり、マス (2, 1) の 1 つ上のマスは存在し、そのマスは空きマスであるため 1 つ上のマスであるマス (1, 1) に移動する。
X の 2 文字目は L であり、マス (1, 1) の 1 つ左のマスは存在しないためマス (1, 1) に留まる。
X の 3 文字目は D であり、マス (1, 1) の 1 つ下のマスは存在し、そのマスは空きマスであるため 1 つ下のマスであるマス (2, 1) に移動する。
X の 4 文字目は R であり、マス (2, 1) の 1 つ右のマスは存在し、そのマスは空きマスであるため 1 つ右のマスであるマス (2, 2) に移動する。
X の 5 文字目は U であり、マス (2, 2) の 1 つ上のマスは存在するが、そのマスは空きマスではないためマス (2, 2) に留まる。

したがって一連の行動を終えた後に高橋君がいるマスはマス (2, 2) です。

入力例 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

出力例 2

2 4

入力例 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

出力例 3

1 1

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

1 \leq H, W \leq 50
1 \leq S_i \leq H
1 \leq S_j \leq W
H, W, S_i, S_j are integers.
C_{i, j} is . or #.
C_{S_i, S_j} = .
X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Input

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

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

Output

Let (x, y) be the cell where Takahashi is after completing the series of actions. Print x and y, separated by a space.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

D - Extended ABC

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

拡張 A 文字列、拡張 B 文字列、拡張 C 文字列および拡張 ABC 文字列を以下のように定義します。

文字列 S が拡張 A 文字列であるとは、S のすべての文字が A であることをいいます。
文字列 S が拡張 B 文字列であるとは、S のすべての文字が B であることをいいます。
文字列 S が拡張 C 文字列であるとは、S のすべての文字が C であることをいいます。
文字列 S が拡張 ABC 文字列であるとは、ある拡張 A 文字列 S _ A 、拡張 B 文字列 S _ B 、拡張 C 文字列 S _ C が存在して、S _ A,S _ B,S _ C をこの順に連結した文字列が S と等しいことをいいます。

例えば、ABC や A 、AAABBBCCCCCCC などは拡張 ABC 文字列ですが、ABBAAAC 、BBBCCCCCCCAAA などは拡張 ABC 文字列ではありません。空文字列は拡張 A 文字列でも拡張 B 文字列でも拡張 C 文字列でもあることに注意してください。

A, B, C からなる文字列 S が与えられます。 S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力してください。

制約

S は A, B, C からなる文字列
1\leq|S|\leq 100\ (|S| は文字列 S の長さ)

入力

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

出力

S が拡張 ABC 文字列ならば Yes を、そうでなければ No を出力せよ。

入力例 1

AAABBBCCCCCCC

出力例 1

Yes

AAABBBCCCCCCC は長さ 3 の拡張 A 文字列 AAA 、長さ 3 の拡張 B 文字列 BBB 、長さ 7 の拡張 C 文字列 CCCCCCC をこの順に連結した文字列なので、拡張 ABC 文字列です。

よって、Yes を出力してください。

入力例 2

ACABABCBC

出力例 2

No

どのような拡張 A 文字列 S _ A, 拡張 B 文字列 S _ B, 拡張 C 文字列 S _ C についても、S _ A,S _ B,S _ C をこの順に連結した文字列が ACABABCBC と等しくなることはありません。

よって、No を出力してください。

入力例 3

出力例 3

Yes

入力例 4

ABBBBBBBBBBBBBCCCCCC

出力例 4

Yes

Score: 200 points

Problem Statement

We define Extended A strings, Extended B strings, Extended C strings, and Extended ABC strings as follows:

A string S is an Extended A string if all characters in S are A.
A string S is an Extended B string if all characters in S are B.
A string S is an Extended C string if all characters in S are C.
A string S is an Extended ABC string if there is an Extended A string S_A, an Extended B string S_B, and an Extended C string S_C such that the string obtained by concatenating S_A, S_B, S_C in this order equals S.

For example, ABC, A, and AAABBBCCCCCCC are Extended ABC strings, but ABBAAAC and BBBCCCCCCCAAA are not. Note that the empty string is an Extended A string, an Extended B string, and an Extended C string.

You are given a string S consisting of A, B, and C. If S is an Extended ABC string, print Yes; otherwise, print No.

Constraints

S is a string consisting of A, B, and C.
1\leq|S|\leq 100 (|S| is the length of the string S.)

Input

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

Output

If S is an Extended ABC string, print Yes; otherwise, print No.

Sample Input 1

AAABBBCCCCCCC

Sample Output 1

Yes

AAABBBCCCCCCC is an Extended ABC string because it is a concatenation of an Extended A string of length 3, AAA, an Extended B string of length 3, BBB, and an Extended C string of length 7, CCCCCCC, in this order.

Thus, print Yes.

Sample Input 2

ACABABCBC

Sample Output 2

No

There is no triple of Extended A string S_A, Extended B string S_B, and Extended C string S_C such that the string obtained by concatenating S_A, S_B, and S_C in this order equals ACABABCBC.

Therefore, print No.

Sample Input 3

Sample Output 3

Yes

Sample Input 4

ABBBBBBBBBBBBBCCCCCC

Sample Output 4

Yes

E - Invisible Hand

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

りんご市場に N 人の売り手と M 人の買い手がいます。

i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。

i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。

次の条件を満たすような最小の整数 X を求めてください。

条件：りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

制約

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

入力

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

N M
A_1 \ldots A_N
B_1 \ldots B_M

出力

答えを出力せよ。

入力例 1

3 4
110 90 120
100 80 120 10000

出力例 1

りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。

110 未満の整数が条件を満たすことはないため、これが答えです。

入力例 2

5 2
100000 100000 100000 100000 100000
100 200

出力例 2

入力例 3

3 2
100 100 100
80 120

出力例 3

Score : 300 points

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

1 \leq N,M \leq 2\times 10^5
1\leq A_i,B_i \leq 10^9
All input values are integers.

Input

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

N M
A_1 \ldots A_N
B_1 \ldots B_M

Output

Print the answer.

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

F - Enumerate Sequences

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

i 番目の要素は 1 以上 R_i 以下
総和が K の倍数

数列の辞書順とは？

数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。

|A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i

制約

入力は全て整数
1 \le N \le 8
2 \le K \le 10
1 \le R_i \le 5

入力

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

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2

出力すべき数列が無い場合もあります。
この場合、出力は空で構いません。

入力例 3

5 5
2 3 2 3 2

出力例 3

Score : 300 points

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

The i-th element is between 1 and R_i, inclusive.
The sum of all elements is a multiple of K.

What is lexicographical order for sequences?

A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

|A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i

Constraints

All input values are integers.
1 \le N \le 8
2 \le K \le 10
1 \le R_i \le 5

Input

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

N K
R_1 R_2 \dots R_N

Output

Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

G - Sum of Maximum Weights

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

N 頂点の木があり、頂点は 1, 2, \dots, N と番号付けられています。
i \, (1 \leq i \leq N - 1) 番目の辺は頂点 u_i と頂点 v_i を結び、重みは w_i です。

異なる頂点 u, v に対し、頂点 u から頂点 v までの最短パスに含まれる辺の重みの最大値を f(u, v) とおきます。

\displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j) を求めてください。

制約

2 \leq N \leq 10^5
1 \leq u_i, v_i \leq N
1 \leq w_i \leq 10^7
与えられるグラフは木である。
入力は全て整数である。

入力

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

N
u_1 v_1 w_1
\vdots
u_{N - 1} v_{N - 1} w_{N - 1}

出力

答えを出力せよ。

入力例 1

3
1 2 10
2 3 20

出力例 1

f(1, 2) = 10, f(2, 3) = 20, f(1, 3) = 20 であるので、これらの和である 50 を出力します。

入力例 2

出力例 2

Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

2 \leq N \leq 10^5
1 \leq u_i, v_i \leq N
1 \leq w_i \leq 10^7
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 w_1
\vdots
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print the answer.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2