AtCoder Daily Training ALL 2026/07/03 16:00start

A - Array

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A = (A_1, A_2, \cdots , A_N) が与えられます。

その後に 1 以上 N 以下の整数 X が与えられます。

A_X の値を出力してください。

制約

1 \le X \le N \le 100
1 \le A_i \le 100
入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N
X

出力

A_X の値を出力せよ。

入力例 1

5
1 2 3 4 5
3

出力例 1

(A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5) です。 A_3 = 3 のため 3 と出力してください。

入力例 2

10
6 6 9 6 10 5 7 2 8 2
4

出力例 2

入力例 3

10
4 4 4 3 4 2 1 1 2 1
10

出力例 3

Score : 100 points

Problem Statement

You are given a sequence A = (A_1, A_2, \cdots , A_N) of length N.

After that, an integer X between 1 and N, inclusive, is given.

Output the value of A_X.

Constraints

1 \le X \le N \le 100
1 \le A_i \le 100
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N
X

Output

Output the value of A_X.

Sample Input 1

5
1 2 3 4 5
3

Sample Output 1

We have (A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5). Since A_3 = 3, output 3.

Sample Input 2

10
6 6 9 6 10 5 7 2 8 2
4

Sample Output 2

Sample Input 3

10
4 4 4 3 4 2 1 1 2 1
10

Sample Output 3

B - Job Interview

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はある会社の採用面接を受けました。

面接官の人数 N と、各面接官の高橋君への評価を表す長さ N の文字列 S が与えられます。
i=1,2,\ldots,N に対し S の i 文字目が i 番目の面接官の評価に対応し、o は「良」、- は「可」、x は「不可」を表します。

高橋君は以下の 2 つの条件を両方満たすならば合格、そうでなければ不合格です。

「良」と評価した面接官が少なくとも 1 人いる
「不可」と評価した面接官がいない

高橋君が合格かどうかを判定してください。

制約

1 \leq N \leq 100
S は o, -, x のみからなる長さが N の文字列

入力

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

N
S

出力

高橋君が合格ならば Yes と、そうでなければ No と出力せよ。

入力例 1

4
oo--

出力例 1

Yes

1, 2 番目の面接官が「良」と評価していて、さらに「不可」と評価した面接官がいないため合格です。

入力例 2

3
---

出力例 2

No

「良」と評価した面接官が 1 人もいないため不合格です。

入力例 3

1
o

出力例 3

Yes

入力例 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

出力例 4

No

100 番目の面接官が「不可」と評価しているため不合格です。

Score : 100 points

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

At least one interviewer's evaluation is Good.
No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of o, -, and x.

Input

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

N
S

Output

If Takahashi passes, print Yes; otherwise, print No.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

C - Piano 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

1\leq N \leq 100
1\leq A_i \leq 100
N,A_i は整数
S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

例えば以下のように演奏することができます。

最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
左手で鍵盤 3 を押す。
右手で鍵盤 6 を押す。
左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
左手で鍵盤 9 を押す。
右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 100
N and A_i are integers.
S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

For example, the performance can be done as follows:

Initially, place the left hand on key 3 and the right hand on key 6.
Press key 3 with the left hand.
Press key 6 with the right hand.
Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
Press key 9 with the left hand.
Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - ASCII Art

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。

H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。

S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。

S_1, S_2, \dots, S_H を順に出力してください。

制約

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
入力される値はすべて整数

入力

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

出力

H 行出力せよ。i 行目には S_i を出力せよ。

入力例 1

2 3
0 1 2
0 0 3

出力例 1

.AB
..C

S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。

入力例 2

出力例 2

X..
.Y.
..Z

入力例 3

出力例 3

B
I
D

入力例 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

Score : 200 points

Problem Statement

You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.

Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.

The j-th character of S_i is a period (.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter is D.)

Print S_1, S_2, \dots, S_H in order.

Constraints

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
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} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

Output

Print H lines. The i-th line should contain S_i.

Sample Input 1

2 3
0 1 2
0 0 3

Sample Output 1

.AB
..C

We have S_1 = .AB and S_2 = ..C. Print these in order.

Sample Input 2

Sample Output 2

X..
.Y.
..Z

Sample Input 3

Sample Output 3

B
I
D

Sample Input 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

E - Matrix Reducing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。

1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。

行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。

A の行を任意に 1 つ選んで削除する。
A の列を任意に 1 つ選んで削除する。

行列 A を行列 B に一致させることができるかどうかを判定して下さい。

制約

1 \leq H_2 \leq H_1 \leq 10
1 \leq W_2 \leq W_1 \leq 10
1 \leq A_{i, j} \leq 10^9
1 \leq B_{i, j} \leq 10^9
入力中の値はすべて整数

入力

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

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

出力

行列 A を行列 B に一致させることができる場合は Yes を、一致させることができない場合は No を出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

出力例 1

Yes

初期状態の行列 A から 2 列目を削除すると、行列 A は

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

となります。そこからさらに 3 行目を削除すると、行列 A は

1 3 4 5
6 8 9 10
16 18 19 20

となります。そこからさらに 1 行目を削除すると、行列 A は

6 8 9 10
16 18 19 20

となります。そこからさらに 4 列目を削除すると、行列 A は

6 8 9
16 18 19

となります。これは行列 B と一致します。操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。

入力例 2

出力例 2

No

どのように操作を行っても、行列 A を行列 B に一致させることはできません。よって、No を出力します。

Score : 300 points

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

Choose an arbitrary row of A and remove it.
Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

1 \leq H_2 \leq H_1 \leq 10
1 \leq W_2 \leq W_1 \leq 10
1 \leq A_{i, j} \leq 10^9
1 \leq B_{i, j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

Output

Print Yes if it is possible to make the matrix A equal the matrix B; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

F - Submask

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。

x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。

制約

N は整数
0 \le N < 2^{60}
N を 2 進数として表記した時、 1 となる位は 15 個以下である

入力

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

出力

答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。

入力例 1

出力例 1

N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。

0000_{(2)}=0_{(10)}
0001_{(2)}=1_{(10)}
0010_{(2)}=2_{(10)}
0011_{(2)}=3_{(10)}
1000_{(2)}=8_{(10)}
1001_{(2)}=9_{(10)}
1010_{(2)}=10_{(10)}
1011_{(2)}=11_{(10)}

入力例 2

出力例 2

入力例 3

576461302059761664

出力例 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

入力は 32bit 符号付き整数に収まらない可能性があります。

Score : 300 points

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

N is an integer.
0 \le N < 2^{60}
In the binary representation of N, at most 15 digit positions contain 1.

Input

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

Output

Print the answer as decimal integers in ascending order, each in its own line.

Sample Input 1

Sample Output 1

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

0000_{(2)}=0_{(10)}
0001_{(2)}=1_{(10)}
0010_{(2)}=2_{(10)}
0011_{(2)}=3_{(10)}
1000_{(2)}=8_{(10)}
1001_{(2)}=9_{(10)}
1010_{(2)}=10_{(10)}
1011_{(2)}=11_{(10)}

Sample Input 2

Sample Output 2

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

G - Moves on Binary Tree

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

頂点数 2^{10^{100}}-1 の完全二分木があり、頂点には 1,2,...,2^{10^{100}}-1 の番号がついています。
頂点 1 が根であり、各 1\leq i < 2^{10^{100}-1} について、頂点 i は頂点 2i を左の子、頂点 2i+1 を右の子として持ちます。

高橋君は最初頂点 X におり、N 回移動を行います。移動は文字列 S により表され、i 回目の移動は次のように行います。

S の i 番目の文字が U のとき、今いる頂点の親に移動する
S の i 番目の文字が L のとき、今いる頂点の左の子に移動する
S の i 番目の文字が R のとき、今いる頂点の右の子に移動する

N 回の移動後に高橋君がいる頂点の番号を求めてください。なお、答えが 10^{18} 以下になるような入力のみが与えられます。

制約

1 \leq N \leq 10^6
1 \leq X \leq 10^{18}
N,X は整数
S は長さ N であり、U,L,R のみからなる
高橋君が根にいるとき、親に移動しようとすることはない
高橋君が葉にいるとき、子に移動しようとすることはない
高橋君が N 回の移動後にいる頂点の番号は 10^{18} 以下である

入力

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

N X
S

出力

答えを出力せよ。

入力例 1

3 2
URL

出力例 1

完全二分木は次のような構造をしています。

各移動により、高橋君がいる頂点の番号は 2 \to 1 \to 3 \to 6 と変化します。

入力例 2

4 500000000000000000
RRUU

出力例 2

500000000000000000

移動の途中過程において、高橋君がいる頂点の番号が 10^{18} を超えることもあります。

入力例 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

出力例 3

126419752371

Score : 400 points

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

If the i-th character of S is U, go to the parent of the vertex he is on now.
If the i-th character of S is L, go to the left child of the vertex he is on now.
If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

1 \leq N \leq 10^6
1 \leq X \leq 10^{18}
N and X are integers.
S has a length of N and consists of U, L, and R.
When Takahashi is at the root, he never attempts to go to the parent.
When Takahashi is at a leaf, he never attempts to go to a child.
The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Input

Input is given from Standard Input in the following format:

N X
S

Output

Print the answer.

Sample Input 1

3 2
URL

Sample Output 1

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

H - Erasing Vertices 2

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。頂点 i には正整数 A_i が書かれています。

あなたは、以下の操作を N 回繰り返します。

まだ削除されていない頂点 x を選び、「頂点 x 」と「頂点 x を端点に持つ辺全て」を削除する。この操作のコストは、頂点 x と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。

N 回の操作全体のコストを、1 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

制約

1 \le N \le 2 \times 10^5
0 \le M \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le U_i,V_i \le N
与えられるグラフは単純。
入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

答えを出力せよ。

入力例 1

出力例 1

以下のように操作を行うことにより、N 回の操作のコストのうちの最大値を 3 にすることができます。

頂点 3 を選ぶ。コストは A_1=3 である。
頂点 1 を選ぶ。コストは A_2+A_4=3 である。
頂点 2 を選ぶ。コストは 0 である。
頂点 4 を選ぶ。コストは 0 である。

N 回の操作のコストのうちの最大値を 2 以下にすることはできないため、解は 3 です。

入力例 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

出力例 2

Score : 500 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

1 \le N \le 2 \times 10^5
0 \le M \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le U_i,V_i \le N
The given graph is simple.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

Sample Output 1

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

Choose Vertex 3. The cost is A_1=3.
Choose Vertex 1. The cost is A_2+A_4=3.
Choose Vertex 2. The cost is 0.
Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

I - Balanced Rectangles

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

H \times W のグリッドが与えられ、各マスには # か . のどちらかが書かれています。
各マスに書かれている記号の情報は H 個の長さ W の文字列 S_1,S_2,\dots,S_H として与えられ、上から i 行目、左から j 列目にあるマスには S_i の j 文字目と同じ記号が書かれています。
このグリッドに対し、以下の条件を全て満たす長方領域がいくつあるか求めてください。

長方領域に含まれる # が書かれたマスの個数と . が書かれたマスの個数が等しい。

厳密には、次の条件を全て満たす 4 つの整数の組 (u,d,l,r) の数を求めてください。

1 \le u \le d \le H
1 \le l \le r \le W
グリッドのうち上から u 行目から d 行目、左から l 列目から r 列目の部分を取り出す。このとき、取り出した部分に含まれる # が書かれたマスの個数と . が書かれたマスの個数が等しい。

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

制約

1 \le T \le 25000
1 \le H,W
ひとつの入力に含まれる H \times W の総和は 3 \times 10^5 を超えない。
S_i は # と . からなる長さ W の文字列である。

入力

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

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

\mathrm{case}_i は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

H W
S_1
S_2
\vdots
S_H

出力

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

入力例 1

3
3 2
##
#.
..
6 6
..#...
..#..#
#.#.#.
.###..
######
.###..
15 50
.......................#...........###.###.###.###
....................#..#..#..........#.#.#...#.#..
.................#...#####...#.....###.#.#.###.###
..................#..##.##..#......#...#.#.#.....#
...................#########.......###.###.###.###
....................#.....#.......................
.###........##......#.....#..#...#.####.####.##..#
#..#.........#......#.....#..#...#.#....#....##..#
#..#.........#......#.....#..#...#.#....#....##..#
#.....##...###..##..#.....#..#...#.#....#....#.#.#
#....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.#
#....#..#.#..#.####.#....##..#...#.#....#....#.#.#
#....#..#.#..#.#....#.....#..#...#.#....#....#..##
#..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..##
.##...##...####.##...####..#..###..####.####.#..##

出力例 1

4
79
4032

この入力には 3 個のテストケースが含まれます。

1 番目のケースについて、以下の 4 個の長方領域が問題文中の条件を満たします。

上から 1 行目から 2 行目、左から 2 列目から 2 列目
上から 2 行目から 3 行目、左から 1 列目から 1 列目
上から 2 行目から 2 行目、左から 1 列目から 2 列目
上から 1 行目から 3 行目、左から 1 列目から 2 列目

Score : 525 points

Problem Statement

You are given an H \times W grid, where each cell contains # or ..
The information about the symbols written in each cell is given as H strings S_1,S_2,\dots,S_H of length W, where the cell in the i-th row from the top and j-th column from the left contains the same symbol as the j-th character of S_i.
Find the number of rectangular regions in this grid that satisfy all of the following conditions:

The number of cells containing # and the number of cells containing . in the rectangular region are equal.

Formally, find the number of quadruples of integers (u,d,l,r) that satisfy all of the following conditions:

1 \le u \le d \le H
1 \le l \le r \le W
When extracting the part of the grid from the u-th through d-th rows from the top and from the l-th through r-th columns from the left, the number of cells containing # and the number of cells containing . in the extracted part are equal.

You are given T test cases. Find the answer for each of them.

Constraints

1 \le T \le 25000
1 \le H,W
The sum of H \times W over all test cases in one input does not exceed 3 \times 10^5.
S_i is a string of length W consisting of # and ..

Input

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

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

\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:

H W
S_1
S_2
\vdots
S_H

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

3
3 2
##
#.
..
6 6
..#...
..#..#
#.#.#.
.###..
######
.###..
15 50
.......................#...........###.###.###.###
....................#..#..#..........#.#.#...#.#..
.................#...#####...#.....###.#.#.###.###
..................#..##.##..#......#...#.#.#.....#
...................#########.......###.###.###.###
....................#.....#.......................
.###........##......#.....#..#...#.####.####.##..#
#..#.........#......#.....#..#...#.#....#....##..#
#..#.........#......#.....#..#...#.#....#....##..#
#.....##...###..##..#.....#..#...#.#....#....#.#.#
#....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.#
#....#..#.#..#.####.#....##..#...#.#....#....#.#.#
#....#..#.#..#.#....#.....#..#...#.#....#....#..##
#..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..##
.##...##...####.##...####..#..###..####.####.#..##

Sample Output 1

4
79
4032

This input contains 3 test cases.

For the 1st case, the following 4 rectangular regions satisfy the conditions in the problem statement:

From the 1st to 2nd rows from the top, from the 2nd to 2nd columns from the left
From the 2nd to 3rd rows from the top, from the 1st to 1st columns from the left
From the 2nd to 2nd rows from the top, from the 1st to 2nd columns from the left
From the 1st to 3rd rows from the top, from the 1st to 2nd columns from the left