AtCoder Daily Training EASY 2025/01/14 19:30start

A - Yay!

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

配点 : 150 点

問題文

英小文字からなる文字列 S が与えられます。ここで S の長さは 3 以上 100 以下です。

S はある 1 文字を除いて全て同じ文字で構成されています。

他のどの文字とも異なる文字は前から何文字目でしょうか。

制約

S は 2 種類の英小文字からなる長さ 3 以上 100 以下の文字列
S はある 1 文字を除いて全て同じ文字

入力

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

出力

答えを出力せよ。

入力例 1

yay

出力例 1

yay の 2 文字目は、1 文字目とも 3 文字目とも異なります。

入力例 2

egg

出力例 2

入力例 3

zzzzzwz

出力例 3

Score: 150 points

Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
All characters but one of S are the same.

Input

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

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

Sample Input 3

zzzzzwz

Sample Output 3

B - Full Moon

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

配点 : 100 点

問題文

高橋くんは満月が好きです。

今日を 1 日目とすると、今日以降で満月を見られる最初の日は M 日目です。以後は P 日ごと、つまり M+P 日目、M+2P 日目、\ldots に満月を見られます。

1 日目から N 日目まで（両端を含む）の中で、高橋くんが満月を見られる日の数を求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq M \leq P \leq 2\times 10^5
入力される数値は全て整数

入力

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

N M P

出力

答えを整数として出力せよ。

入力例 1

13 3 5

出力例 1

満月を見られる日は、3 日目、8 日目、13 日目、18 日目、\ldots です。

1 日目から 13 日目までの中で高橋くんが満月を見られる日は、3 日目、8 日目、13 日目の 3 個です。

入力例 2

5 6 6

出力例 2

高橋くんが満月を見られる日が存在しない場合もあります。

入力例 3

200000 314 318

出力例 3

Score : 100 points

Problem Statement

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

1\leq N\leq 2\times 10^5
1\leq M \leq P \leq 2\times 10^5
All input values are integers.

Input

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

N M P

Output

Print the answer as an integer.

Sample Input 1

13 3 5

Sample Output 1

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

C - Prefix and Suffix

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

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)

S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。

S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。

制約

1 \leq N \leq M \leq 100
S は英小文字からなる長さ N の文字列
T は英小文字からなる長さ M の文字列

入力

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

N M
S
T

出力

問題文の指示に従って答えを出力せよ。

入力例 1

3 7
abc
abcdefg

出力例 1

S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。

入力例 2

3 4
abc
aabc

出力例 2

S は T の接尾辞ですが接頭辞ではありません。

入力例 3

3 3
abc
xyz

出力例 3

S は T の接頭辞でも接尾辞でもありません。

入力例 4

3 3
aaa
aaa

出力例 4

S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

1 \leq N \leq M \leq 100
S is a string of length N consisting of lowercase English letters.
T is a string of length M consisting of lowercase English letters.

Input

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

N M
S
T

Output

Print the answer according to the instructions in the problem statement.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

S and T may coincide, in which case S is both a prefix and a suffix of T.

D - Star or Not

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

配点 : 200 点

問題文

N 頂点 N-1 辺の木が与えられます。
頂点には 1,2,\ldots,N の番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。

注記

「木」については、Wikipedia「木(数学)」を参照してください。

制約

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
与えられるグラフは木である

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

与えられたグラフがスターであるなら Yes と、スターでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えられたグラフはスターです。

入力例 2

出力例 2

No

与えられたグラフはスターではありません。

入力例 3

出力例 3

Yes

Score : 200 points

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

If the given graph is a star, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

Sample Output 2

No

The given graph is not a star.

Sample Input 3

Sample Output 3

Yes

E - PC on the Table

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

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

1\leq H \leq 100
2\leq W \leq 100
H と W は整数である
S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

解が複数存在する場合、どれを出力しても正答とみなされる。

入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。

入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

1\leq H \leq 100
2\leq W \leq 100
H and W are integers.
S_i is a string of length W consisting of . and T.

Input

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

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC