AtCoder Daily Training HARD 2024/01/18 20:30start

E - Product

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。

それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が X になるような取り出し方は何通りありますか？

ただし、書かれた数が同じであっても全てのボールは区別します。

制約

N \geq 2
L_i \geq 2
袋に入っているボールの個数の総積は 10^5 を超えない。すなわち、\displaystyle\prod_{i=1}^{N}L_i \leq 10^5
1 \leq a_{i,j} \leq 10^9
1 \leq X \leq 10^{18}
入力に含まれる値は全て整数である。

入力

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

N X
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}

出力

答えを出力せよ。

入力例 1

2 40
3 1 8 4
2 10 5

出力例 1

袋 1 の 3 番目のボールと袋 2 の 1 番目のボールを選ぶと、a_{1,3} \times a_{2,1} = 4 \times 10 = 40 となります。
袋 1 の 2 番目のボールと袋 2 の 2 番目のボールを選ぶと、a_{1,2} \times a_{2,2} = 8 \times 5 = 40 となります。
これ以外に総積が 40 になる取り出し方は存在しないので、答えは 2 です。

入力例 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

出力例 2

書かれた数が同じであっても全てのボールは区別することに注意してください。

入力例 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

出力例 3

総積が X になる取り出し方が 1 つも存在しないこともあります。

Score : 300 points

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

N \geq 2
L_i \geq 2
The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
1 \leq a_{i,j} \leq 10^9
1 \leq X \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
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}

Output

Print the answer.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

There may be no way to make the product X.

F - Festival

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)

i=1,2,\dots,N に対して、以下の問題を解いてください。

i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。

制約

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
入力は全て整数

入力

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

N M
A_1 A_2 \dots A_M

出力

N 行出力せよ。

i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。

入力例 1

3 2
2 3

出力例 1

1
0
0

AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。

1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。

入力例 2

8 5
1 3 4 7 8

出力例 2

Score : 250 points

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
All input values are integers.

Input

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

N M
A_1 A_2 \dots A_M

Output

Print N lines.

The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

G - Three Days Ago

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

20230322 は並べ替えると 02320232 となり、これは 0232 を 2 度繰り返しています。
このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を 2 度繰り返すようにできるものを 嬉しい列 と呼びます。
数字のみからなる文字列 S が与えられるので、以下の条件を全て満たす整数の組 (l,r) はいくつあるか求めてください。

1 \le l \le r \le |S| ( |S| は S の長さ)
S の l 文字目から r 文字目までの (連続する) 部分文字列は嬉しい列である。

制約

S は数字のみからなる長さ 1 以上 5 \times 10^5 以下の文字列

入力

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

出力

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

入力例 1

20230322

出力例 1

S= 20230322 です。
条件を満たす整数組 (l,r) は (1,6),(1,8),(2,7),(7,8) の 4 つです。

入力例 2

0112223333444445555556666666777777778888888889999999999

出力例 2

S の先頭が 0 である場合もあります。

入力例 3

3141592653589793238462643383279502884197169399375105820974944

出力例 3

Score : 400 points

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

1 \le l \le r \le |S|. (|S| is the length of S.)
The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Input

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

Output

Print an integer representing the answer.

Sample Input 1

20230322

Sample Output 1

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

H - Roulettes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 台のルーレットがあります。 i 番目 (1\leq i\leq N) のルーレットには P _ i 個の整数 S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} が書かれており、C _ i 円支払うことで 1 回プレイできます。 i 番目のルーレットを 1 回プレイすると、1 以上 P _ i 以下の整数 j が一様ランダムに選ばれ、S _ {i,j} ポイントを得ることができます。

ルーレットで得られるポイントは、過去の結果と独立に決まります。

高橋くんは、ポイントを M ポイント以上獲得したいです。高橋くんは、M ポイント以上獲得するまでに支払う金額をなるべく小さくするように行動します。ただし、高橋くんはルーレットをプレイするたびこれまでのルーレットの結果を見て次にプレイするルーレットを選ぶことができます。

高橋くんがポイントを M ポイント以上獲得するまでに支払う金額の期待値を求めてください。

より厳密な定義

より厳密には、次のようになります。高橋くんがルーレットを選ぶ戦略を決めるごとに、その戦略で M ポイント以上獲得するまでに支払う金額の期待値 E が次のように定義されます。

自然数 X に対して、その戦略に従って高橋くんが M ポイント以上獲得するか、ルーレットを X 回プレイするまでに支払う金額の期待値を f(X) とする。E=\displaystyle\lim _ {X\to+\infty}f(X) とする。

この問題の条件のもとで、高橋くんがどのような戦略をとっても \displaystyle\lim _ {X\to+\infty}f(X) が有限の値になることが証明できます。高橋くんが E を最小にするような戦略をとったときの E の値を求めてください。

制約

1\leq N\leq 100
1\leq M\leq 100
1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
1\leq P _ i\leq 100\ (1\leq i\leq N)
0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
\displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
入力はすべて整数

入力

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

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

出力

高橋くんが M ポイント以上獲得するまでに支払う金額の期待値を 1 行で出力せよ。出力された値と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき、正答と判定される。

入力例 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

出力例 1

215.913355350494384765625

例えば、高橋くんはルーレットを次のようにプレイすることができます。

50 円を支払ってルーレット 2 をプレイする。S _ {2,4}=8 ポイントを得る。
50 円を支払ってルーレット 2 をプレイする。S _ {2,1}=1 ポイントを得る。
100 円を支払ってルーレット 1 をプレイする。S _ {1,1}=5 ポイントを得る。得たポイントの合計が 8+1+5\geq14 ポイントとなったため、終了する。

この例では、14 ポイントを得るまでに 200 円を支払っています。

出力と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき正答と判定されるため、215.9112 や 215.9155 などと出力しても正解になります。

入力例 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

出力例 2

100 ポイントが出るまでルーレット 2 を回し続けるのが最適です。

入力例 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

出力例 3

45037.072314895291126319493887599716

Score : 475 points

Problem Statement

There are N roulette wheels. The i-th (1\leq i\leq N) wheel has P _ i integers S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} written on it, and you can play it once by paying C _ i yen. When you play the i-th wheel once, an integer j between 1 and P _ i, inclusive, is chosen uniformly at random, and you earn S _ {i,j} points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least M points. Takahashi will act to minimize the amount of money he pays before he earns at least M points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least M points.

More formal definition

Here is a more formal statement. For a strategy that Takahashi can adopt in choosing which wheel to play, the expected amount of money E that he pays before he earns at least M points with that strategy is defined as follows.

For a natural number X, let f(X) be the expected amount of money Takahashi pays before he earns at least M points or plays the wheels X times in total according to that strategy. Let E=\displaystyle\lim _ {X\to+\infty}f(X).

Under the conditions of this problem, it can be proved that \displaystyle\lim _ {X\to+\infty}f(X) is finite no matter what strategy Takahashi adopts. Find the value of E when he adopts a strategy that minimizes E.

Constraints

1\leq N\leq 100
1\leq M\leq 100
1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
1\leq P _ i\leq 100\ (1\leq i\leq N)
0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
\displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
All input values are integers.

Input

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

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

Output

Print the expected amount of money Takahashi will pay until he earns at least M points in a single line. Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}.

Sample Input 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

Pay 50 yen to play roulette 2 and earn S _ {2,4}=8 points.
Pay 50 yen to play roulette 2 and earn S _ {2,1}=1 point.
Pay 100 yen to play roulette 1 and earn S _ {1,1}=5 points. He has earned a total of 8+1+5\geq14 points, so he quits playing.

In this case, he pays 200 yen before earning 14 points.

Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}, so outputs such as 215.9112 and 215.9155 would also be considered correct.

Sample Input 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

Sample Output 2

It is optimal to keep spinning roulette 2 until you get 100 points.

Sample Input 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

Sample Output 3

45037.072314895291126319493887599716

I - Parenthesis Checking

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

空文字列
ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

( と ) のみからなる長さ N の文字列 S があります。

Q 個のクエリ \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q が与えられるので、順番に処理してください。クエリには 2 種類があり、入力形式とクエリの内容は以下の通りです。

1 l r : S の l 文字目と r 文字目を入れ替える。
2 l r : S の l 文字目から r 文字目までの連続部分文字列が正しい括弧列であるか判定する。

制約

1 \leq N,Q \leq 2 \times 10^5
S は ( と ) のみからなる長さ N の文字列
1 \leq l < r \leq N
N,Q,l,r はいずれも整数
各クエリは 1 l r、2 l r のいずれかの形式で与えられる。
2 l r の形式のクエリは 1 つ以上与えられる。

入力

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

N Q
S
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q

出力

2 l r の形式の各クエリに対して、連続部分文字列が正しい括弧列である場合 Yes、そうでない場合 No と出力し、改行せよ。

入力例 1

出力例 1

Yes
No
No

1 つ目のクエリにおいて、(()) は正しい括弧列です。

2 つ目のクエリにおいて、(( は正しい括弧列ではありません。

3 つ目のクエリにおいて、)( は正しい括弧列ではありません。

入力例 2

出力例 2

Yes
No

1 つ目のクエリにおいて、(()) は正しい括弧列です。

2 つ目のクエリによって、S は )()(( となります。

3 つ目のクエリにおいて、)()( は正しい括弧列ではありません。

入力例 3

出力例 3

Yes
No
No

Score : 500 points

Problem Statement

Let us define a correct parenthesis sequence as a string that satisfies one of the following conditions.

It is an empty string.
It is a concatenation of (, A, ), in this order, for some correct parenthesis sequence A.
It is a concatenation of A, B, in this order, for some correct parenthesis sequences A and B.

We have a string S of length N consisting of ( and ).

Given Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q, process them in order. There are two kinds of queries, with the following formats and content.

1 l r: Swap the l-th and r-th characters of S.
2 l r: Determine whether the contiguous substring from the l-th through the r-th character is a correct parenthesis sequence.

Constraints

1 \leq N,Q \leq 2 \times 10^5
S is a string of length N consisting of ( and ).
1 \leq l < r \leq N
N,Q,l,r are all integers.
Each query is in the format 1 l r or 2 l r.
There is at least one query in the format 2 l r.

Input

Input is given from Standard Input in the following format:

N Q
S
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q

Output

For each query in the format 2 l r, print Yes if the contiguous substring is a correct parenthesis sequence, and No otherwise, followed by a newline.

Sample Input 1

Sample Output 1

Yes
No
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, (( is not a correct parenthesis sequence.

In the third query, )( is not a correct parenthesis sequence.

Sample Input 2

Sample Output 2

Yes
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, S becomes )()((.

In the third query, )()( is not a correct parenthesis sequence.

Sample Input 3

Sample Output 3

Yes
No
No