AtCoder Daily Training ALL 2026/02/12 18:00start

A - 202<s>3</s>

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

配点 : 100 点

問題文

英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。

制約

S は英小文字と数字からなる長さ 4 以上 100 以下の文字列
S は 2023 で終わる。

入力

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

出力

答えを出力せよ。

入力例 1

hello2023

出力例 1

hello2024

hello2023 の最後の文字を 4 に変更すると、 hello2024 となります。

入力例 2

worldtourfinals2023

出力例 2

worldtourfinals2024

入力例 3

出力例 3

S が 2023 で終わることが保証されていますが、 S が 2023 そのものである場合もあります。

入力例 4

20232023

出力例 4

20232024

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
S ends with 2023.

Input

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

Output

Print the answer.

Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.

Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

Sample Output 3

S is guaranteed to end with 2023, possibly being 2023 itself.

Sample Input 4

20232023

Sample Output 4

20232024

B - Happy Birthday! 4

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

配点 : 100 点

問題文

正整数 X,Y,Z が与えられます。

高橋君と青木君は現在それぞれ X 歳、Y 歳です。

高橋君と青木君は毎年 1 月 1 日を迎えると同時に 1 歳ずつ歳を取ります。

（今年も含めて）これから高橋君の年齢が青木君の年齢のちょうど Z 倍となるタイミングが存在するか判定してください。

制約

1\le X,Y \le 100
2\le Z\le 10
入力される値は全て整数

入力

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

X Y Z

出力

高橋君の年齢が青木君の年齢のちょうど Z 倍となるタイミングが存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

44 20 2

出力例 1

Yes

今から 4 年後に高橋君は 48 歳、青木君は 24 歳になり、高橋君の年齢は青木君の年齢のちょうど 2 倍になります。したがって、 Yes を出力してください。

入力例 2

28 10 3

出力例 2

No

これから高橋君の年齢が青木君の年齢のちょうど 3 倍となるタイミングは存在しません。したがって、No を出力してください。

入力例 3

50 5 10

出力例 3

Yes

現在の高橋君の年齢は青木君の年齢のちょうど 10 倍です。

今年も含めてこれから高橋君の年齢が青木君の年齢のちょうど Z 倍となるタイミングが存在するか判定することに注意してください。

入力例 4

1 100 2

出力例 4

No

Score : 100 points

Problem Statement

You are given positive integers X,Y,Z.

Takahashi and Aoki are currently X years old and Y years old, respectively.

Takahashi and Aoki age by 1 year simultaneously on every January 1st.

Determine whether there is a moment in the future (including this year) when Takahashi's age becomes exactly Z times Aoki's age.

Constraints

1\le X,Y \le 100
2\le Z\le 10
All input values are integers.

Input

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

X Y Z

Output

Output Yes if there is a moment in the future when Takahashi's age becomes exactly Z times Aoki's age, and No otherwise.

Sample Input 1

44 20 2

Sample Output 1

Yes

Four years from now, Takahashi will be 48 years old and Aoki will be 24 years old, so Takahashi's age will be exactly twice Aoki's age. Thus, output Yes.

Sample Input 2

28 10 3

Sample Output 2

No

There will never be a moment when Takahashi's age becomes exactly three times Aoki's age. Thus, output No.

Sample Input 3

50 5 10

Sample Output 3

Yes

Currently, Takahashi's age is exactly 10 times Aoki's age.

Note that you need to determine whether there will be such a moment in the future including this year.

Sample Input 4

1 100 2

Sample Output 4

No

C - Compression

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

配点 : 150 点

問題文

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

A に含まれる数を重複を除いて小さい順に出力してください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A に含まれる数を小さい順に C_1,C_2,\ldots , C_M として、以下の形式で出力せよ。

M
C_1 C_2 \ldots C_M

入力例 1

4
3 1 4 1

出力例 1

3
1 3 4

A=(3,1,4,1) に含まれる数は小さい順に 1,3,4 の 3 つです。したがって、上記のように出力してください。

入力例 2

3
7 7 7

出力例 2

1
7

入力例 3

8
19 5 5 19 5 19 4 19

出力例 3

3
4 5 19

Score : 150 points

Problem Statement

An integer sequence A=(A_1,A_2,\ldots,A_N) of length N is given.

Output the numbers contained in A in ascending order, removing duplicates.

Constraints

1\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

Output

Let C_1,C_2,\ldots , C_M be the numbers contained in A in ascending order. Output in the following format:

M
C_1 C_2 \ldots C_M

Sample Input 1

4
3 1 4 1

Sample Output 1

3
1 3 4

The numbers contained in A=(3,1,4,1) are 1,3,4 in ascending order, totalling 3 distinct numbers. Therefore, output as shown above.

Sample Input 2

3
7 7 7

Sample Output 2

1
7

Sample Input 3

8
19 5 5 19 5 19 4 19

Sample Output 3

3
4 5 19

D - Counting Arrays

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

配点 : 200 点

問題文

1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L_i で j (1 \leq j \leq L_i) 番目の要素が a_{i,j} であるような数列です。

数列 i と数列 j は、 L_i = L_j かつすべての k (1 \leq k \leq L_i) に対して a_{i,k} = a_{j,k} が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から数列 N の中に全部で何種類の数列がありますか？

制約

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
すべての数列の要素の個数の和、すなわち \sum_{i=1}^N L_i は 2 \times 10^5 を超えない。
入力はすべて整数である。

入力

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

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

出力

数列の種類数を出力せよ。

入力例 1

出力例 1

入力例 1 で与えられている数列は以下の 4 個です。

数列 1 : (1, 2)
数列 2 : (1, 1)
数列 3 : (2, 1)
数列 4 : (1, 2)

このうち数列 1 と数列 4 は同じ数列で、それ以外は互いに異なる数列なので全部で 3 種類の数列があります。

入力例 2

出力例 2

入力例 2 で与えられている数列は以下の 5 個です。

数列 1 : (1)
数列 2 : (1)
数列 3 : (2)
数列 4 : (1, 1)
数列 5 : (1, 1, 1)

入力例 3

1
1 1

出力例 3

Score : 200 points

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

Output

Print the number of different sequences.

Sample Input 1

Sample Output 1

Sample Input 1 contains four sequences:

Sequence 1 : (1, 2)
Sequence 2 : (1, 1)
Sequence 3 : (2, 1)
Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

Sample Output 2

Sample Input 2 contains five sequences:

Sequence 1 : (1)
Sequence 2 : (1)
Sequence 3 : (2)
Sequence 4 : (1, 1)
Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

E - kasaka

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

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 S の先頭に a をいくつか（ 0 個でも良い）つけ加えて回文にすることができるか判定してください。

ただし、長さ N の文字列 A=A_1A_2\ldots A_N が回文であるとは、すべての 1\leq i\leq N について A_i=A_{N+1-i} が成り立っていることをいいます。

制約

1 \leq \lvert S \rvert \leq 10^6
S は英小文字のみからなる。

入力

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

出力

S の先頭に a をいくつかつけ加えて回文にすることができるならば Yes を、そうでないならば No を出力せよ。

入力例 1

kasaka

出力例 1

Yes

kasaka の先頭に a を 1 つ付け加えることによって、akasaka となり回文となるため Yes を出力します。

入力例 2

atcoder

出力例 2

No

atcoder の先頭に a をいくつ付け加えても回文となる事はありません。

入力例 3

php

出力例 3

Yes

php はそれ自体回文です。S の先頭に付け加える a は 0 個でも許されるため、Yes を出力します。

Score : 300 points

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

1 \leq \lvert S \rvert \leq 10^6
S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

If adding some number of a's (possibly zero) at the beginning of S can make it a palindrome, print Yes; otherwise, print No.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

F - Dice Sum

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

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

1\le A_i \le M (1 \le i \le N)
\displaystyle\sum _{i=1}^N A_i \leq K

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

1 \leq N, M \leq 50
N \leq K \leq NM
入力は全て整数

入力

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

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 3 4

出力例 1

条件を満たす数列は以下の 6 つです。

(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)

入力例 2

31 41 592

出力例 2

798416518

答えを 998244353 で割った余りを出力してください。

Score : 300 points

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

1\le A_i \le M (1 \le i \le N)
\displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

1 \leq N, M \leq 50
N \leq K \leq NM
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

The following six sequences satisfy the conditions.

(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

G - Unicyclic Components

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

配点 : 400 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。

このグラフのすべての連結成分が次の条件を満たすかどうかを判定してください。

その連結成分に含まれる頂点の個数と辺の本数が等しい。

注釈

無向グラフ とは、辺に向きの無いグラフのことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i \leq v_i \leq N
入力はすべて整数

入力

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

N M
u_1 v_1
\vdots
u_M v_M

出力

すべての連結成分が条件を満たすならば Yes と、そうでなければ No と出力せよ。

入力例 1

出力例 1

Yes

このグラフには頂点 1 のみからなる連結成分と頂点 2,3 からなる連結成分があります。
前者には 1 本の辺(辺 2 )が、後者には 2 本の辺(辺 1,3 )が含まれており、条件を満たします。

入力例 2

出力例 2

Yes

入力例 3

出力例 3

No

Score : 400 points

Problem Statement

You are given an undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.

Determine whether every connected component in this graph satisfies the following condition.

The connected component has the same number of vertices and edges.

Notes

An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i \leq v_i \leq N
All values in the input are integers.

Input

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

N M
u_1 v_1
\vdots
u_M v_M

Output

If every connected component satisfies the condition, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The graph has a connected component formed from just vertex 1, and another formed from vertices 2 and 3.
The former has one edge (edge 2), and the latter has two edges (edges 1 and 3), satisfying the condition.

Sample Input 2

Sample Output 2

Yes

Sample Input 3

Sample Output 3

No

H - Christmas Color Grid 1

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

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

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

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

1 \leq H,W \leq 1000
S_{i,j} = . または S_{i,j} = #
S_{i,j} = . なる (i,j) が存在する。

入力

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。

入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。

入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean?

It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

1 \leq H,W \leq 1000
S_{i,j} = . or S_{i,j} = #.
There is at least one (i,j) such that S_{i,j} = ..

Input

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

I - Dangerous Sugoroku

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

配点 : 550 点

問題文

N 個のマスが 1 列に並んでおり、順に 1, 2, \ldots, N の番号が付けられています。

M 個の整数組 (L_1, R_1), \ldots, (L_M, R_M) が与えられます。

マス j はある i に対して L_i \leq j \leq R_i を満たすとき、またそのときに限り 悪いマス であると定めます。

マス 1 から以下の行動を繰り返すことでマス N に移動できるか判定してください。

現在位置しているマスをマス x とする。以下の条件をすべて満たすような整数 i を選び、マス x + i に移動する。
- A \leq i \leq B
- x + i \leq N
- マス x + i は悪いマスでない

制約

2 \leq N \leq 10^{12}
0 \leq M \leq 2 \times 10^4
1 \leq A \leq B \leq 20
1 < L_i \leq R_i < N (1 \leq i \leq M)
R_i < L_{i + 1} (1 \leq i \leq M - 1)
入力される値はすべて整数

入力

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

N M A B
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

問題文中の行動を繰り返すことでマス N に移動できる場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

24 2 3 5
7 8
17 20

出力例 1

Yes

マス 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24 のように移動することでマス N に移動することができます。

入力例 2

30 1 5 8
4 24

出力例 2

No

入力例 3

100 4 10 11
16 18
39 42
50 55
93 99

出力例 3

Yes

Score : 550 points

Problem Statement

There are N squares arranged in a row, labeled 1, 2, \ldots, N from left to right.

You are given M pairs of integers (L_1, R_1), \ldots, (L_M, R_M).

A square j is defined to be bad if and only if there exists some i such that L_i \leq j \leq R_i.

Determine whether you can move from square 1 to square N by repeatedly performing the following action:

Let your current square be x. Choose an integer i that satisfies all of the following conditions, and move to square x + i.
- A \leq i \leq B
- x + i \leq N
- Square x + i is not bad.

Constraints

2 \leq N \leq 10^{12}
0 \leq M \leq 2 \times 10^4
1 \leq A \leq B \leq 20
1 < L_i \leq R_i < N \ (1 \leq i \leq M)
R_i < L_{i+1} \ (1 \leq i \leq M - 1)
All input values are integers.

Input

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

N M A B
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

If it is possible to reach square N by repeating the action described in the problem statement, print Yes. Otherwise, print No.

Sample Input 1

24 2 3 5
7 8
17 20

Sample Output 1

Yes

You can move to square N in this way: 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24.

Sample Input 2

30 1 5 8
4 24

Sample Output 2

No

Sample Input 3

100 4 10 11
16 18
39 42
50 55
93 99

Sample Output 3

Yes