AtCoder Daily Training EASY 2025/10/02 20:30start

A - Seats

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

配点 : 100 点

問題文

N 個の座席が並んでおり、座席には 1, 2, \ldots, N の番号が付けられています。

座席の状態は #, . からなる長さ N の文字列 S によって与えられます。S の i 文字目が # のとき座席 i には人が座っていることを表し、S の i 文字目が . のとき座席 i には人が座っていないことを表します。

1 以上 N - 2 以下の整数 i であって、以下の条件を満たすものの個数を求めてください。

座席 i, i + 2 には人が座っており、座席 i + 1 には人が座っていない

制約

N は 1 以上 2 \times 10^5 以下の整数
S は #, . からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

6
#.##.#

出力例 1

i = 1, 4 が条件を満たすので、答えは 2 です。

入力例 2

1
#

出力例 2

入力例 3

9
##.#.#.##

出力例 3

Score : 100 points

Problem Statement

There are N seats in a row, numbered 1, 2, \ldots, N.

The state of the seats is given by a string S of length N consisting of # and .. If the i-th character of S is #, it means seat i is occupied; if it is ., seat i is unoccupied.

Find the number of integers i between 1 and N - 2, inclusive, that satisfy the following condition:

Seats i and i + 2 are occupied, and seat i + 1 is unoccupied.

Constraints

N is an integer satisfying 1 \leq N \leq 2 \times 10^5.
S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.

Sample Input 1

6
#.##.#

Sample Output 1

i = 1 and 4 satisfy the condition, so the answer is 2.

Sample Input 2

1
#

Sample Output 2

Sample Input 3

9
##.#.#.##

Sample Output 3

B - Arithmetic Progression

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

配点 : 100 点

問題文

初項が A、末項が B、公差が D であるような等差数列を出力してください。

なお、そのような等差数列が存在する入力のみが与えられます。

制約

1 \leq A \leq B \leq 100
1\leq D \leq 100
初項が A、末項が B、公差が D であるような等差数列が存在する
入力は全て整数

入力

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

A B D

出力

初項が A、末項が B、公差が D であるような等差数列の項を順に空白区切りで出力せよ。

入力例 1

3 9 2

出力例 1

3 5 7 9

初項が 3、末項が 9、公差が 2 であるような等差数列は (3,5,7,9) です。

入力例 2

10 10 1

出力例 2

初項が 10、末項が 10、公差が 1 であるような等差数列は (10) です。

Score: 100 points

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

1 \leq A \leq B \leq 100
1 \leq D \leq 100
There is an arithmetic sequence with first term A, last term B, and common difference D.
All input values are integers.

Input

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

A B D

Output

Print the terms of the arithmetic sequence with first term A, last term B, and common difference D, in order, separated by spaces.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

C - racecar

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

配点 : 200 点

問題文

英小文字のみからなる N 個の文字列 S_1,S_2,\ldots,S_N が与えられます。
1 以上 N 以下の 相異なる 整数 i,j であって、S_i と S_j をこの順に連結した文字列が回文となるようなものが存在するか判定してください。

ただし、長さ M の文字列 T が回文であるとは、任意の 1\leq i\leq M について、T の i 文字目と (M+1-i) 文字目が一致していることをいいます。

制約

2\leq N\leq 100
1\leq \lvert S_i\rvert \leq 50
N は整数
S_i は英小文字のみからなる文字列
S_i はすべて異なる。

入力

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

N
S_1
S_2
\vdots
S_N

出力

問題文の条件をみたす i,j が存在するならば Yes を、そうでないならば No を出力せよ。

入力例 1

5
ab
ccef
da
a
fe

出力例 1

Yes

(i,j)=(1,4) とすると、S_1=ab と S_4=a をこの順に連結した文字列は aba となり、これは回文であるため条件をみたしています。
よって、Yes を出力します。

また、(i,j)=(5,2) としても、S_5=fe と S_2=ccef をこの順に連結した文字列は feccef となり、やはり条件をみたしています。

入力例 2

3
a
b
aba

出力例 2

No

S_1, S_2, S_3 のうち、どの相異なる 2 つの文字列を繋げても回文となりません。よって、No を出力します。
問題文における i,j は相異なる必要があることに注意してください。

入力例 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

出力例 3

Yes

Score : 200 points

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

2\leq N\leq 100
1\leq \lvert S_i\rvert \leq 50
N is an integer.
S_i is a string consisting of lowercase English letters.
All S_i are distinct.

Input

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

N
S_1
S_2
\vdots
S_N

Output

If there are i and j that satisfy the condition in the problem statement, print Yes; otherwise, print No.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

D - Playing Cards Validation

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

配点 : 200 点

問題文

英大文字および数字からなる 2 文字の文字列が N 個与えられます。i 個目の文字列は S_i です。
以下の 3 つの条件をすべて満たすか判定してください。
・すべての文字列に対して、1 文字目は H , D , C , S のどれかである。
・すべての文字列に対して、2 文字目は A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , K のどれかである。
・すべての文字列は相異なる。つまり、i \neq j ならば S_i \neq S_j である。

制約

1 \leq N \leq 52
S_i は英大文字および数字からなる 2 文字の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

3 つの条件をすべて満たす場合は Yes、そうでない場合は No を出力せよ。

入力例 1

4
H3
DA
D3
SK

出力例 1

Yes

このとき 3 つの条件をすべて満たすことが確認できます。

入力例 2

5
H3
DA
CK
H3
S7

出力例 2

No

S_1 と S_4 がともに H3 となってしまっているため、3 番目の条件に反します。

入力例 3

4
3H
AD
3D
KS

出力例 3

No

入力例 4

5
00
AA
XX
YY
ZZ

出力例 4

No

Score : 200 points

Problem Statement

You are given N strings, each of length 2, consisting of uppercase English letters and digits. The i-th string is S_i.
Determine whether the following three conditions are all satisfied.
・For every string, the first character is one of H, D, C, and S.
・For every string, the second character is one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K.
・All strings are pairwise different. That is, if i \neq j, then S_i \neq S_j.

Constraints

1 \leq N \leq 52
S_i is a string of length 2 consisting of uppercase English letters and digits.

Input

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

N
S_1
S_2
\vdots
S_N

Output

If the three conditions are all satisfied, print Yes; otherwise, print No.

Sample Input 1

4
H3
DA
D3
SK

Sample Output 1

Yes

One can verify that the three conditions are all satisfied.

Sample Input 2

5
H3
DA
CK
H3
S7

Sample Output 2

No

Both S_1 and S_4 are H3, violating the third condition.

Sample Input 3

4
3H
AD
3D
KS

Sample Output 3

No

Sample Input 4

5
00
AA
XX
YY
ZZ

Sample Output 4

No

E - Path Graph?

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

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

パスグラフとは

頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
整数 i, j が 1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
入力される値は全て整数
入力で与えられるグラフは単純

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00

入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01

入力例 3

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph?

A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:

For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
All values in the input are integers.
The graph given in the input is simple.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print Yes if the given graph is a path graph; print No otherwise.

Sample Input 1

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01

Sample Input 3

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02