AtCoder Daily Training ALL 2026/10/29 16:00start

A - Appender

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

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。

以下のようにして決まる文字列 T を出力してください。

S の末尾の文字が e である場合、T は S の末尾に r を付け加えた文字列である。
S の末尾の文字が e でない場合、T は S の末尾に er を付け加えた文字列である。

制約

S は英小文字からなる文字列
S の長さは 1 以上 10 以下

入力

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

出力

答えを出力せよ。

入力例 1

live

出力例 1

liver

live の末尾の文字は e なので、live の末尾に r を付け加えた文字列 liver が出力するべき文字列 T です。

入力例 2

femur

出力例 2

femurer

femur の末尾の文字は e ではないので、femur の末尾に er を付け加えた文字列 femurer が出力するべき文字列 T です。

入力例 3

chimpanzee

出力例 3

chimpanzeer

chimpanzee の末尾の文字は e なので、chimpanzee の末尾に r を付け加えた文字列 chimpanzeer が出力するべき文字列 T です。

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Output the string T determined as follows.

If the last character of S is e, T is the string obtained by appending r to the end of S.
If the last character of S is not e, T is the string obtained by appending er to the end of S.

Constraints

S is a string consisting of lowercase English letters.
The length of S is between 1 and 10, inclusive.

Input

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

Output

Output the answer.

Sample Input 1

live

Sample Output 1

liver

The last character of live is e, so the string liver, obtained by appending r to the end of live, is the string T to be outputted.

Sample Input 2

femur

Sample Output 2

femurer

The last character of femur is not e, so the string femurer, obtained by appending er to the end of femur, is the string T to be outputted.

Sample Input 3

chimpanzee

Sample Output 3

chimpanzeer

The last character of chimpanzee is e, so the string chimpanzeer, obtained by appending r to the end of chimpanzee, is the string T to be outputted.

B - Hell, World!

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

配点 : 100 点

問題文

1 以上 10 以下の整数 X が与えられます。

HelloWorld という文字列から X 文字目だけを削除した文字列を出力してください。

制約

X は 1 以上 10 以下の整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

HellWorld

HelloWorld の 5 文字目を削除すると HellWorld になります。したがって、HellWorld を出力してください。

入力例 2

出力例 2

HelloWord

入力例 3

出力例 3

elloWorld

Score : 100 points

Problem Statement

You are given an integer X between 1 and 10, inclusive.

Output the string obtained by deleting only the X-th character from the string HelloWorld.

Constraints

X is an integer between 1 and 10, inclusive.

Input

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

Output

Output the answer.

Sample Input 1

Sample Output 1

HellWorld

Deleting the 5-th character of HelloWorld gives HellWorld. Thus, output HellWorld.

Sample Input 2

Sample Output 2

HelloWord

Sample Input 3

Sample Output 3

elloWorld

C - Prefix?

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

配点 : 200 点

問題文

英小文字のみからなる 2 つの文字列 S, T が与えられます。 S が T の接頭辞かどうかを判定してください。

接頭辞とは

長さ N の文字列 T_1T_2\ldots T_N の接頭辞とは、 0 \leq i \leq N を満たすある整数 i によって、T の先頭 i 文字目までの文字列 T_1T_2\ldots T_i として表される文字列です。例えば、T = abc のとき、T の接頭辞は、空文字列、a 、ab 、abc の 4 つです。

制約

S と T はそれぞれ英小文字のみからなる長さが 1 以上 100 以下の文字列

入力

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

S
T

出力

S が T の接頭辞である場合は Yes を、そうでない場合は No を出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

atco
atcoder

出力例 1

Yes

atco は atcoder の接頭辞です。よって、Yes を出力します。

入力例 2

code
atcoder

出力例 2

No

code は atcoder の接頭辞ではありません。よって、No を出力します。

入力例 3

abc
abc

出力例 3

Yes

文字列全体もその文字列の接頭辞であることに注意してください。

入力例 4

aaaa
aa

出力例 4

No

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

What is a prefix?

A prefix of a string T_1T_2\ldots T_N of length N is a string expressed as the first i characters of T, T_1T_2\ldots T_i, where i is an integer such that 0 \leq i \leq N. For example, when T = abc, there are four prefixes of T: an empty string, a, ab, and abc.

Constraints

S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

Print Yes if S is a prefix of T; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

D - ASCII Art

実行時間制限: 2 sec / メモリ制限: 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 - Count xxx

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

配点 : 300 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。

S の空でない部分文字列であって、1 種類の文字のみからなるものの数を求めてください。ただし、文字列として等しい部分文字列同士は、取り出し方が異なっても区別しません。

なお、S の空でない部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のうち、長さが 1 以上であるもののことをいいます。例えば、ab や abc は abc の空でない部分文字列ですが、ac や空文字列は abc の空でない部分文字列ではありません。

制約

1 \leq N \leq 2\times 10^5
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

S の空でない部分文字列であって、1 種類の文字のみからなるものの数を出力せよ。

入力例 1

6
aaabaa

出力例 1

S の空でない部分文字列であって、1 種類の文字のみからなるものは a, aa, aaa, b の 4 つです。 S から a や aa を取り出す方法は 1 通りではありませんが、それぞれ 1 回ずつしか数えないことに注意してください。

入力例 2

1
x

出力例 2

入力例 3

12
ssskkyskkkky

出力例 3

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of non-empty substrings of S that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of S is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

1 \leq N \leq 2\times 10^5
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the number of non-empty substrings of S that are repetitions of one character.

Sample Input 1

6
aaabaa

Sample Output 1

The non-empty substrings of S that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from S, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

Sample Input 3

12
ssskkyskkkky

Sample Output 3

F - Dislike Foods

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

配点 : 300 点

問題文

AtCoderレストランでは 1 から N までの番号がつけられている N 種類の食材を扱っています。

また、AtCoderレストランでは 1 から M までの番号がつけられている M 個の料理を提供しています。料理 i には K_i 種類の食材が使われており、食材 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} が使われています。

すぬけくんは現在 N 種類の食材がすべて苦手です。また、すぬけ君は苦手な食材が 1 種類でも使われている料理を食べることができず、苦手な食材が 1 種類も使われていない料理を食べることができます。

すぬけ君はこれから N 日間かけて苦手な食材を克服しようとしています。すぬけ君は i 日目に食材 B_i を克服し、それ以降苦手な食材でなくなります。

i=1,2,\ldots,N について以下の値を求めてください。

i 日目にすぬけ君が食材 B_i を克服した直後、すぬけ君が食べることができるAtCoderレストランの料理の個数

制約

1 \leq N \leq 3 \times 10^{5}
1 \leq M \leq 3 \times 10^{5}
1 \leq K_i \leq N (1 \leq i \leq M)
K_i の総和は 3 \times 10^{5} 以下
1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
1 \leq B_i \leq N (1 \leq i \leq N)
B_i \neq B_j (i \neq j )
入力は全て整数

入力

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

N M
K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
K_M A_{M,1} A_{M,2} \ldots A_{M,K_M}
B_1 B_2 \ldots B_N

出力

N 行出力せよ。k 行目には、i=k のときの値を出力せよ。

入力例 1

出力例 1

以下のようにすぬけ君は苦手な食材を克服します。

1 日目: 食材 1 を克服する。このとき、どの料理にも苦手な食材が使われているため 0 を出力する。
2 日目: 食材 3 を克服する。このとき、料理 4 は苦手な食材が使われなくなるため食べられるようになる。料理 4 以外の料理は苦手な食材が使われているため、 1 を出力する。
3 日目: 食材 2 を克服する。このとき、料理 1 は苦手な食材が使われなくなるため食べられるようになる。料理 1,4 以外の料理は苦手な食材が使われているため、 2 を出力する。
4 日目: 食材 5 を克服する。このとき、料理 3 は苦手な食材が使われなくなるため食べられるようになる。料理 1,3,4 以外の料理は苦手な食材が使われているため、 3 を出力する。
5 日目: 食材 4 を克服する。このとき、料理 2 は苦手な食材が使われなくなるため食べられるようになる。全ての料理に苦手な食材が使われていないため、 4 を出力する。

入力例 2

9 8
1 4
5 6 9 7 4 3
4 2 4 1 3
1 1
5 7 9 8 1 5
2 9 8
1 2
1 1
6 5 2 7 8 4 1 9 3

出力例 2

Score : 300 points

Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

1 \leq N \leq 3 \times 10^{5}
1 \leq M \leq 3 \times 10^{5}
1 \leq K_i \leq N (1 \leq i \leq M)
The sum of K_i is at most 3 \times 10^{5}.
1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
1 \leq B_i \leq N (1 \leq i \leq N)
B_i \neq B_j (i \neq j )
All input values are integers.

Input

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

N M
K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
K_M A_{M,1} A_{M,2} \ldots A_{M,K_M}
B_1 B_2 \ldots B_N

Output

Print N lines. The k-th line should contain the answer for i=k.

Sample Input 1

Sample Output 1

Snuke overcomes his disliked ingredients as follows:

Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 2

9 8
1 4
5 6 9 7 4 3
4 2 4 1 3
1 1
5 7 9 8 1 5
2 9 8
1 2
1 1
6 5 2 7 8 4 1 9 3

Sample Output 2

G - Yet Another Recursive Function

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

配点 : 400 点

問題文

非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。

f(0) = 1
任意の正整数 k に対し f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)

ここで、\lfloor A \rfloor は A の小数点以下を切り捨てた値を指します。

このとき、 f(N) を求めてください。

制約

N は 0 \le N \le 10^{18} を満たす整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

A function f(x) defined for non-negative integers x satisfies the following conditions.

f(0) = 1.
f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.

Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.

Find f(N).

Constraints

N is an integer satisfying 0 \le N \le 10^{18}.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

H - Roads and Gates

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

配点 : 450 点

問題文

AtCoder 国には N 個の都市と M 本の道路があります。 i 本目の道路 (1\le i\le M) は都市 u _ i と都市 v _ i を双方向に繋いでおり、一方からもう一方へ T _ i 分かけて移動することができます。

また、それぞれの都市にはワープゲートが設置されており、都市 i\ (1\le i\le N) から都市 j\ (1\le j\le N) へワープゲートを使って X _ i+X _ j+Y 分かけて移動することができます。

これ以外の方法で AtCoder 国の都市の間を移動することはできません。

k=2,3,\ldots,N について、次の問題を解いてください。

都市 1 から都市 k へ移動するのにかかる時間の最小値を求めよ。

ただし、道路やワープゲートから同じ都市の別の道路やワープゲートへ移動するのにかかる時間は無視できるものとします。

制約

2\le N\le2\times10 ^ 5
0\le M\le2\times10 ^ 5
1\le u _ i\lt v _ i\le N\ (1\le i\le M)
1\le T _ i\le10 ^ 9\ (1\le i\le M)
1\le X _ i\le10 ^ 9\ (1\le i\le N)
1\le Y\le 10 ^ 9
入力はすべて整数

入力

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

N M Y
u _ 1 v _ 1 T _ 1
u _ 2 v _ 2 T _ 2
\vdots
u _ M v _ M T _ M
X _ 1 X _ 2 \ldots X _ N

出力

k=2,3,\ldots,N に対する問題の答えを、この順に空白を区切りとして出力せよ。

入力例 1

7 7 3
1 2 1
1 3 6
2 3 4
3 5 8
3 7 4
4 5 2
4 7 9
3 1 4 1 5 9 2

出力例 1

1 5 6 8 14 7

例えば、都市 1 から都市 7 へは次のようにして 7 分で移動することができます。

1 本目の道路を使い、1 分かけて都市 1 から都市 2 へ移動する。
ワープゲートを使い、1+2+3=6 分かけて都市 2 から都市 7 へ移動する。

都市 1 から都市 7 へ 6 分以下で移動することはできないため、k=7 に対する問題の答えは 7 です。

入力例 2

2 0 1000000000
1000000000 1000000000

出力例 2

3000000000

答えが 2 ^ {31} 以上になる場合があることに注意してください。

入力例 3

12 20 873
2 7 940
6 9 444
6 11 809
7 8 786
9 10 468
7 10 234
6 10 660
4 12 939
8 10 896
1 11 953
8 10 818
4 8 967
3 9 724
6 7 929
3 4 948
1 3 999
10 11 724
7 10 338
1 8 967
1 12 733
581 978 950 629 583 729 554 712 438 930 774 279

出力例 3

2432 999 1672 2037 1762 1753 967 1723 1677 953 733

Score : 450 points

Problem Statement

The country of AtCoder has N cities and M roads. The i-th road (1\le i\le M) connects cities u _ i and v _ i bidirectionally, and allows travel from one to the other in T _ i minutes.

Additionally, each city has a warp gate installed, and you can travel from city i\ (1\le i\le N) to city j\ (1\le j\le N) using the warp gate in X _ i+X _ j+Y minutes.

There are no other ways to travel between cities in the country.

For each k=2,3,\ldots,N, solve the following problem:

Find the minimum time required to travel from city 1 to city k.

The time required to transfer from a road or warp gate to another road or warp gate at the same city is negligible.

Constraints

2\le N\le2\times10 ^ 5
0\le M\le2\times10 ^ 5
1\le u _ i\lt v _ i\le N\ (1\le i\le M)
1\le T _ i\le10 ^ 9\ (1\le i\le M)
1\le X _ i\le10 ^ 9\ (1\le i\le N)
1\le Y\le 10 ^ 9
All input values are integers.

Input

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

N M Y
u _ 1 v _ 1 T _ 1
u _ 2 v _ 2 T _ 2
\vdots
u _ M v _ M T _ M
X _ 1 X _ 2 \ldots X _ N

Output

Output the answers to the problems for k=2,3,\ldots,N in this order, separated by spaces.

Sample Input 1

7 7 3
1 2 1
1 3 6
2 3 4
3 5 8
3 7 4
4 5 2
4 7 9
3 1 4 1 5 9 2

Sample Output 1

1 5 6 8 14 7

For example, you can travel from city 1 to city 7 in 7 minutes as follows:

Use the first road to travel from city 1 to city 2 in 1 minute.
Use the warp gate to travel from city 2 to city 7 in 1+2+3=6 minutes.

It is impossible to travel from city 1 to city 7 in 6 minutes or less, so the answer for k=7 is 7.

Sample Input 2

2 0 1000000000
1000000000 1000000000

Sample Output 2

3000000000

Note that the answer may be 2 ^ {31} or greater.

Sample Input 3

12 20 873
2 7 940
6 9 444
6 11 809
7 8 786
9 10 468
7 10 234
6 10 660
4 12 939
8 10 896
1 11 953
8 10 818
4 8 967
3 9 724
6 7 929
3 4 948
1 3 999
10 11 724
7 10 338
1 8 967
1 12 733
581 978 950 629 583 729 554 712 438 930 774 279

Sample Output 3

2432 999 1672 2037 1762 1753 967 1723 1677 953 733

I - Starry Landscape Photo

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

配点 : 500 点

問題文

AtCoder 星から見える夜空には N 個の星があり、これらの N 個の星は東から西へ一直線上に並んでいます。東から i 番目 (1\le i\le N) の星は、これらの星の中で B _ i 番目に明るい星です。

高橋くんは、次のような手順で夜空の写真を撮ることにしました。

1\le l\le r\le N を満たす整数の組 (l,r) を選び、東から l 番目、l+1 番目、\ldots、r 番目の星が全てフレームに収まり、他の星がフレームに入らないようにカメラを設置する。
1\le b\le N を満たす整数 b を選び、N 個の星のうち明るさが 1 番目から b 番目に入る（かつフレームに収まっている）星がすべて写り、そうでない星が写らないようにシャッターを開放する。

ただし、星が 1 つも写らないように写真を撮ることはできません。

このようにして撮影された夜空の写真に写っている星の集合としてありえるものが何通りあるか求めてください。

制約

1\le N\le5\times10 ^ 5
1\le B _ i\le N\ (1\le i\le N)
B _ i\ne B _ j\ (1\le i\lt j\le N)
入力はすべて整数

入力

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

N
B _ 1 B _ 2 \ldots B _ N

出力

答えを出力せよ。

入力例 1

4
3 1 4 2

出力例 1

例えば (l,r)=(2,4),b=3 とすると、東から 2 番目の星と東から 4 番目の星の 2 つの星が写った写真を撮ることができます。

これを含め、以下の 12 通りの星の集合が写った写真を撮ることができます。それぞれの写真ではより東にある星がより左側に並んでおり、i 番目に明るい星に整数 i が書かれています。

これ以外の集合を撮ることはできないため、12 を出力してください。

入力例 2

7
1 2 3 4 5 6 7

出力例 2

入力例 3

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

出力例 3

Score : 500 points

Problem Statement

In the night sky seen from planet AtCoder, there are N stars, and these N stars are arranged in a line from east to west. The i-th star from the east (1\le i\le N) is the B _ i-th brightest among these stars.

Takahashi decided to take a picture of the night sky using the following procedure:

Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and set up the camera so that the l-th, (l+1)-th, \ldots, r-th stars from the east all fit in the frame, and no other stars enter the frame.
Choose an integer b satisfying 1\le b\le N, and open the shutter so that all stars among the N stars whose brightness ranks from 1st through b-th (and that fit in the frame) are captured, and no other stars are captured.

However, he may not take a picture with no stars captured.

Find the number of different sets of stars that can be captured in pictures taken in this way.

Constraints

1\le N\le5\times10 ^ 5
1\le B _ i\le N\ (1\le i\le N)
B _ i\ne B _ j\ (1\le i\lt j\le N)
All input values are integers.

Input

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

N
B _ 1 B _ 2 \ldots B _ N

Output

Print the answer.

Sample Input 1

4
3 1 4 2

Sample Output 1

For example, with (l,r)=(2,4),b=3, you can take a picture with two stars: the 2nd star from the east and the 4th star from the east.

Including this, you can take pictures with the following 12 different sets of stars. In each picture, stars further east are arranged further left, and the i-th brightest star is labeled with integer i.

No other sets can be captured, so print 12.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

Sample Input 3

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