AtCoder Daily Training ALL 2026/09/08 16:00start

A - Alloy

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

配点 : 100 点

問題文

高橋くんは A グラムの純金と B グラムの純銀 (0 \leq A,B,\ 0 \lt A+B) をよく溶かした上で混ぜ合わせ、新たな金属を生成しました。

生成された金属は「純金」「純銀」「合金」のいずれでしょうか？

なお、生成された金属は

0 \lt A かつ B=0 なら「純金」
A=0 かつ 0 \lt B なら「純銀」
0 \lt A かつ 0 \lt B なら「合金」

であるとみなします。

制約

0 \leq A,B \leq 100
0 \lt A+B
A,B は整数

入力

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

A B

出力

生成された金属が「純金」なら Gold と、「純銀」なら Silver と、「合金」なら Alloy と出力せよ。

入力例 1

50 50

出力例 1

Alloy

0 \lt A かつ 0 \lt B であるため、生成された金属は「合金」です。

入力例 2

100 0

出力例 2

Gold

0 \lt A かつ B=0 であるため、生成された金属は「純金」です。

入力例 3

0 100

出力例 3

Silver

A=0 かつ 0 \lt B であるため、生成された金属は「純銀」です。

入力例 4

100 2

出力例 4

Alloy

Score : 100 points

Problem Statement

Takahashi melted and mixed A grams of gold and B grams of silver (0 \leq A,B,\ 0 \lt A+B) to produce new metal.

What metal did he produce: pure gold, pure silver, or an alloy?

Formally, the product is called as follows.

Pure gold, if 0 \lt A and B=0.
Pure silver, if A=0 and 0 \lt B.
An alloy, if 0 \lt A and 0 \lt B.

Constraints

0 \leq A,B \leq 100
1 \leq A+B
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

If the product is pure gold, print Gold; if it is pure silver, print Silver; if it is an alloy, print Alloy.

Sample Input 1

50 50

Sample Output 1

Alloy

We have 0 \lt A and 0 \lt B, so the product is an alloy.

Sample Input 2

100 0

Sample Output 2

Gold

We have 0 \lt A and B=0, so the product is pure gold.

Sample Input 3

0 100

Sample Output 3

Silver

We have A=0 and 0 \lt B, so the product is pure silver.

Sample Input 4

100 2

Sample Output 4

Alloy

B - Subsegment Reverse

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

配点 : 100 点

問題文

正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,\dots,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。

制約

入力は全て整数
1 \le L \le R \le N \le 100

入力

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

N L R

出力

操作後の数列を A'=(A'_1,A'_2,\dots,A'_N) として、以下の形式で出力せよ。

A'_1 A'_2 \dots A'_N

入力例 1

5 2 3

出力例 1

1 3 2 4 5

最初、 A=(1,2,3,4,5) です。
2 項目から 3 項目までを逆順に並べ替えた後の数列は (1,3,2,4,5) なので、これを出力してください。

入力例 2

7 1 1

出力例 2

1 2 3 4 5 6 7

L=R である場合もあります。

入力例 3

10 1 10

出力例 3

10 9 8 7 6 5 4 3 2 1

L=1 や R=N である場合もあります。

Score : 100 points

Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

All input values are integers.
1 \leq L \leq R \leq N \leq 100

Input

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

N L R

Output

Let A' = (A'_1, A'_2, \dots, A'_N) be the sequence after the operation. Print it in the following format:

A'_1 A'_2 \dots A'_N

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

C - A^A

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

配点 : 200 点

問題文

整数 B が与えられます。
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力してください。

制約

1 \leq B \leq 10^{18}
B は整数

入力

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

出力

A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力せよ。
A^A = B を満たす正の整数 A が複数ある場合は、どれを出力しても正解とみなされる。

入力例 1

出力例 1

3^3 = 27 なので 3 を出力します。

入力例 2

出力例 2

-1

A^A = B を満たす A は存在しません。

入力例 3

10000000000

出力例 3

Score : 200 points

Problem Statement

You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.

Constraints

1 \leq B \leq 10^{18}
B is an integer.

Input

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

Output

If there exists a positive integer A such that A^A = B, print its value; otherwise, print -1.
If there are multiple positive integers A such that A^A = B, any of them will be accepted.

Sample Input 1

Sample Output 1

3^3 = 27, so print 3.

Sample Input 2

Sample Output 2

-1

There is no A such that A^A = B.

Sample Input 3

10000000000

Sample Output 3

D - Arrays

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

配点 : 200 点

問題文

N 個の数列 A_1, A_2, \ldots, A_N が与えられます。

数列 A_i の長さは L_i であり A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}) です。

その後、整数 X, Y が与えられます。 A_{X,Y} の値を出力してください。

制約

1 \le N \le 2 \times 10^5
1 \le L_i
L_i の総和は 2 \times 10^5 以下
1 \le A_{i,j} \le 1000
1 \le X \le N
1 \le Y \le L_X
入力される値はすべて整数

入力

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

N
L_1 A_{1,1} A_{1,2} \ldots A_{1,L_1}
L_2 A_{2,1} A_{2,2} \ldots A_{2,L_2}
\vdots
L_N A_{N,1} A_{N,2} \ldots A_{N,L_N}
X Y

出力

A_{X,Y} の値を出力せよ。

入力例 1

出力例 1

(A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)) です。
A_3 = (5, 6, 7, 8) であり、 A_{3,4} = 8 なので 8 を出力してください。

入力例 2

出力例 2

A_2 = (8, 2, 6) なので、A_{2,2} = 2 です。

入力例 3

1
5 100 200 300 400 500
1 5

出力例 3

Score : 200 points

Problem Statement

You are given N sequences A_1, A_2, \ldots, A_N.

The length of sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}).

After that, integers X and Y are given. Output the value of A_{X,Y}.

Constraints

1 \le N \le 2 \times 10^5
1 \le L_i
The sum of L_i is at most 2 \times 10^5.
1 \le A_{i,j} \le 1000
1 \le X \le N
1 \le Y \le L_X
All input values are integers.

Input

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

N
L_1 A_{1,1} A_{1,2} \ldots A_{1,L_1}
L_2 A_{2,1} A_{2,2} \ldots A_{2,L_2}
\vdots
L_N A_{N,1} A_{N,2} \ldots A_{N,L_N}
X Y

Output

Output the value of A_{X,Y}.

Sample Input 1

Sample Output 1

We have (A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)).
Since A_3 = (5, 6, 7, 8) and A_{3,4} = 8, output 8.

Sample Input 2

Sample Output 2

Since A_2 = (8, 2, 6), we have A_{2,2} = 2.

Sample Input 3

1
5 100 200 300 400 500
1 5

Sample Output 3

E - Snake Queue

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

配点 : 300 点

問題文

ヘビの待ち行列があります。最初、列は空です。

クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 3 種類です。

タイプ 1 : 1 l の形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。
タイプ 2 : 2 の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。
タイプ 3 : 3 k の形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。

制約

1 \leq Q \leq 3 \times 10^{5}
タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
タイプ 2 のクエリにおいて、列が空でないことが保証される
タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
入力は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。

1 l

3 k

出力

タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。

入力例 1

出力例 1

5
10

1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。

入力例 2

出力例 2

タイプ 3 のクエリが 1 つもない場合もあります。

入力例 3

出力例 3

20
5

Score : 300 points

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

1 \leq Q \leq 3 \times 10^{5}
For a query of type 1, 1 \leq l \leq 10^{9}
For a query of type 2, it is guaranteed that the queue is not empty.
For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, \text{query}_i is the i-th query in one of the following forms:

1 l

3 k

Output

Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.

Sample Input 1

Sample Output 1

5
10

1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

Sample Output 3

20
5

F - digitnum

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

配点 : 300 点

問題文

整数 N が与えられるので、以下の問題を解いてください。

f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。

制約

N は整数
1 \le N < 10^{18}

入力

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

出力

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

入力例 1

出力例 1

1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
- これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
- これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。

結局、求める答えは 73 です。

入力例 2

出力例 2

入力例 3

999999999999999999

出力例 3

762062362

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

N is an integer.
1 \le N < 10^{18}

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
- Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
- Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

Sample Output 2

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

G - Pre-Palindrome

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

配点 : 400 点

問題文

以下の条件を満たす英小文字からなる文字列を良い文字列とします。

1 文字以下を書き換えることで回文にすることができる。

例えば a、iwai、abcdcza などは良い文字列ですが、abcd、atcoder などは良い文字列ではありません。特に、回文も良い文字列であることに注意してください。

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

S の空でない部分文字列（連続な部分列）であって良い文字列であるものの個数を求めてください。

2 つの部分文字列は、S から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。

部分文字列とは

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

制約

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

入力

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

出力

答えを出力せよ。

入力例 1

ababa

出力例 1

S の 2 文字目から 3 文字目までの ba や 1 文字目から 5 文字目までの ababa などが良い文字列です。

良い文字列は部分文字列 15 通りのうち 1 文字目から 4 文字目までの abab、2 文字目から 5 文字目までの baba を除く 13 通りです。

入力例 2

atcoder

出力例 2

入力例 3

abccbacbacb

出力例 3

Score : 400 points

Problem Statement

A string consisting of lowercase English letters is called a good string if it satisfies the following condition.

It can be turned into a palindrome by rewriting at most one character.

For example, a, iwai, and abcdcza are good strings, but abcd and atcoder are not good strings. Note that, in particular, a palindrome is also a good string.

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

Find the number of non-empty substrings (contiguous subsequences) of S that are good strings.

Two substrings taken from different positions of S are counted separately even if they are equal as strings.

What is a substring?

A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

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

Input

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

Output

Output the answer.

Sample Input 1

ababa

Sample Output 1

The substring ba from the 2nd through 3rd characters of S and the substring ababa from the 1st through 5th characters are some good strings.

Among the 15 substrings, the good strings are the 13 substrings other than abab from the 1st through 4th characters and baba from the 2nd through 5th characters.

Sample Input 2

atcoder

Sample Output 2

Sample Input 3

abccbacbacb

Sample Output 3

H - Random Swaps of Balls

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

配点 : 450 点

問題文

N - 1 個の白いボールと 1 個の黒いボールがあります。これらの N 個のボールが横一列に並んでおり、はじめ黒いボールが最も左にあります。

高橋くんは、これから以下の操作をちょうど K 回行います。

1 以上 N 以下の整数を一様ランダムに選ぶ試行を 2 回行う。選んだ整数をそれぞれ a, b とする。さらに、 a \neq b であれば左から a 番目のボールと b 番目のボールを交換する。

K 回の操作のあと黒いボールがある位置を左から x 番目とします。x の期待値を \text{mod} \ 998244353 で求めてください。

期待値 \text{mod} \ 998244353 とは

求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

1 \leq N \leq 998244352
1 \leq K \leq 10^5

入力

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

N K

出力

答えを 1 行に出力せよ。

入力例 1

2 1

出力例 1

499122178

1 回の操作が終わった後、黒いボールが左から 1 番目にある確率、 2 番目にある確率はそれぞれ \displaystyle \frac{1}{2} です。よって期待値は \displaystyle \frac{3}{2} です。

入力例 2

3 2

出力例 2

554580198

入力例 3

4 4

出力例 3

592707587

Score : 450 points

Problem Statement

There are N - 1 white balls and one black ball. These N balls are arranged in a row, with the black ball initially at the leftmost position.

Takahashi will perform the following operation exactly K times.

Choose an integer uniformly at random between 1 and N, inclusive, twice. Let a and b the chosen integers. If a \neq b, swap the a-th and b-th balls from the left.

After K operations, let the black ball be at the x-th position from the left. Find the expected value of x, modulo 998244353.

What is expected value modulo 998244353?

It can be proved that the sought expected value will always be rational. Additionally, under the constraints of this problem, it can be proved that if this value is expressed as an irreducible fraction \frac{P}{Q}, then Q \not \equiv 0 \pmod{998244353}. Therefore, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

1 \leq N \leq 998244352
1 \leq K \leq 10^5

Input

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

N K

Output

Print the answer in one line.

Sample Input 1

2 1

Sample Output 1

499122178

After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both \displaystyle \frac{1}{2}. Thus, the expected value is \displaystyle \frac{3}{2}.

Sample Input 2

3 2

Sample Output 2

554580198

Sample Input 3

4 4

Sample Output 3

592707587

I - Components

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

配点 : 500 点

問題文

N 頂点の木があります。頂点には 1 から N までの番号が付いており、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

x=1,2,\ldots,N に対して次の問題を解いてください。

木の頂点の部分集合 V であって空でないものは 2^N-1 通り存在するが、そのうち V による誘導部分グラフの連結成分数が x であるようなものは何通りあるかを 998244353 で割った余りを求めよ。

誘導部分グラフとは

S をグラフ G の頂点の部分集合とします。このとき、G の S による誘導部分グラフとは、頂点集合が S で、辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです。

制約

1 \leq N \leq 5000
1 \leq a_i \lt b_i \leq N
与えられるグラフは木

入力

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

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

出力

N 行出力せよ。
i 行目には x=i に対する出力をせよ。

入力例 1

出力例 1

以下の 5 通りでは誘導部分グラフの連結成分数が 2、これら以外では 1 になります。

V = \{1,2,4\}
V = \{1,3\}
V = \{1,3,4\}
V = \{1,4\}
V = \{2,4\}

入力例 2

2
1 2

出力例 2

3
0

入力例 3

出力例 3

Score : 500 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects vertex a_i and vertex b_i.

Solve the following problem for each x=1,2,\ldots,N:

There are (2^N-1) non-empty subsets V of the tree's vertices. Find the number, modulo 998244353, of such V that the subgraph induced by V has exactly x connected components.

What is an induced subgraph?

Let S be the subset of the vertices of a graph G; then the subgraph of G induced by S is a graph whose vertex set is S and whose edge set consists of all edges of G whose both ends are contained in S.

Constraints

1 \leq N \leq 5000
1 \leq a_i \lt b_i \leq N
The given graph is a tree.

Input

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

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

Output

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

Sample Input 1

Sample Output 1

The induced subgraph will have two connected components in the following five cases and one in the others.

V = \{1,2,4\}
V = \{1,3\}
V = \{1,3,4\}
V = \{1,4\}
V = \{2,4\}

Sample Input 2

2
1 2

Sample Output 2

3
0

Sample Input 3

Sample Output 3