AtCoder Daily Training MEDIUM 2025/08/06 20:00start

C - 3-smooth Numbers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正の整数 N が与えられます。 N=2^x3^y を満たす整数 x,y が存在するなら Yes 、そうでなければ No と出力してください。

制約

1\leq N\leq10^{18}
N は整数

入力

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

出力

条件を満たす整数 x,y が存在するなら Yes 、そうでなければ No と 1 行に出力せよ。

入力例 1

出力例 1

Yes

x=2,y=4 とすると、2^x3^y=2^23^4=4\times81=324 となるため条件を満たします。よって、Yes と出力してください。

入力例 2

出力例 2

No

どのような整数 x,y をとっても 2^x3^y=5 とすることはできません。よって、No と出力してください。

入力例 3

出力例 3

Yes

x=5,y=0 とすると、2^x3^y=32\times1=32 となるため、Yes と出力してください。

入力例 4

37748736

出力例 4

Yes

Score : 200 points

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

1\leq N\leq10^{18}
N is an integer.

Input

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

Output

Print a single line containing Yes if there are integers x and y that satisfy the condition, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

D - Maintain Multiple Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項は a_{i, j} です。

Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。

制約

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
入力は全て整数

入力

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

出力

Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

7
5

1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。

1 番目の数列の第 3 項は 7 です。
2 番目の数列の第 1 項は 5 です。

入力例 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

出力例 2

Score : 200 points

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
All values in the input are integers.

Input

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

Output

Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.

Sample Input 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

The 3-rd term of the 1-st sequence is 7.
The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

E - Loong Tracking

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は座標平面上で龍を操作するゲームを作成しました。

龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭と呼びます。

最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。

1 C: 頭を方向 C に 1 移動させる。ここで、C は R, L, U, D のいずれかであり、それぞれ x 軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i\ \ (2\leq i \leq N) は移動前にパーツ i-1 があった座標に移動する。
2 p: パーツ p のある座標を求める。

制約

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
1 種類目のクエリにおいて、C は R, L, U, D のいずれか
2 種類目のクエリにおいて、1\leq p \leq N
入力に含まれる数値は全て整数

入力

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式である。

1 C

2 p

出力

2 種類目のクエリの回数を q として q 行出力せよ。
i 行目には、i 番目のそのようなクエリに対する答えの座標を (x,y) としたとき、x,y を空白区切りで出力せよ。

入力例 1

出力例 1

2 種類目のクエリを処理する各タイミングにおいて、パーツの位置は次のようになっています。

複数のパーツが同じ座標に存在しうることに注意してください。

Score : 300 points

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
2 p: Find the coordinates of part p.

Constraints

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
For the first type of query, C is one of R, L, U, and D.
For the second type of query, 1\leq p \leq N.
All numerical input values are integers.

Input

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 C

2 p

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.

Sample Input 1

Sample Output 1

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

F - Avoid K Palindrome 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

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

S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。

ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。

制約

2\leq K \leq N \leq 10
N,K は整数
S は英小文字のみからなる長さ N の文字列

入力

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

N K
S

出力

S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。

入力例 1

3 2
aab

出力例 1

aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。

入力例 2

5 3
zzyyx

出力例 2

zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。

入力例 3

10 5
abcwxyzyxw

出力例 3

Score : 300 points

Problem Statement

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

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

2 \leq K \leq N \leq 10
N and K are integers.
S is a string of length N consisting only of lowercase English letters.

Input

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

N K
S

Output

Print the number of strings obtained by permuting S that do not contain a palindrome of length K as a substring.

Sample Input 1

3 2
aab

Sample Output 1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

G - Doubles

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個のサイコロがあります。 i 番目のサイコロは K_i 個の面をもち、各面にはそれぞれ A_{i,1},A_{i,2},\ldots,A_{i,K_i} が書かれています。このサイコロを振ると、各面がそれぞれ \frac{1}{K_i} の確率で出ます。

あなたは N 個のサイコロから 2 個を選んで振ります。サイコロを適切に選んだときの、2 つのサイコロの出目が等しくなる確率の最大値を求めてください。

制約

2 \leq N \leq 100
1 \leq K_i
K_1+K_2+\dots+K_N \leq 10^5
1 \leq A_{i,j} \leq 10^5
入力は全て整数である

入力

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

N
K_1 A_{1,1} A_{1,2} \dots A_{1,K_1}
\vdots
K_N A_{N,1} A_{N,2} \dots A_{N,K_N}

出力

答えを出力せよ。真の解との相対誤差または絶対誤差が 10^{-8} 以下のとき正解とみなされる。

入力例 1

3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6

出力例 1

0.333333333333333

1 番目のサイコロと 2 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{3} です。
1 番目のサイコロと 3 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{6} です。
2 番目のサイコロと 3 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{6} です。

よって最大値は \frac{1}{3}=0.3333333333\ldots となります。

入力例 2

3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2

出力例 2

0.666666666666667

Score : 400 points

Problem Statement

There are N dice. The i-th die has K_i faces, with the numbers A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} written on them. When you roll this die, each face appears with probability \frac{1}{K_i}.

You choose two dice from the N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints

2 \leq N \leq 100
1 \leq K_i
K_1 + K_2 + \dots + K_N \leq 10^5
1 \leq A_{i,j} \leq 10^5
All input values are integers.

Input

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

N
K_1 A_{1,1} A_{1,2} \dots A_{1,K_1}
\vdots
K_N A_{N,1} A_{N,2} \dots A_{N,K_N}

Output

Print the answer. Your answer is considered correct if the absolute or relative error from the true solution does not exceed 10^{-8}.

Sample Input 1

3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6

Sample Output 1

0.333333333333333

When choosing the 1st and 2nd dice, the probability that the outcomes are the same is \frac{1}{3}.
When choosing the 1st and 3rd dice, the probability is \frac{1}{6}.
When choosing the 2nd and 3rd dice, the probability is \frac{1}{6}.

Therefore, the maximum probability is \frac{1}{3} = 0.3333333333\ldots.

Sample Input 2

3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2

Sample Output 2

0.666666666666667