AtCoder Daily Training HARD 2026/01/20 17:30start

E - Sowing Stones

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N まで番号がつけられた N 個のマスが一列に並んでいます。最初、 M 個のマスに石が入っており、マス X_i には A_i 個 (1 \leq i \leq M) の石が入っています。

あなたは以下の操作を好きな回数( 0 回でもよい)行うことができます。

マス i (1 \leq i \leq N-1) に石があるとき、マス i から石を 1 つマス i+1 に移動させる。

N 個のマスすべてに石がちょうど 1 個ずつ入っている状態にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は -1 を出力してください。

制約

2 \leq N \leq 2 \times 10^{9}
1 \leq M \leq 2 \times 10^{5}
M \leq N
1 \leq X_i \leq N (1 \leq i \leq M)
X_i \neq X_j (1 \leq i < j \leq M)
1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
入力は全て整数

入力

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

N M
X_1 X_2 \ldots X_M
A_1 A_2 \ldots A_M

出力

答えを出力せよ。

入力例 1

5 2
1 4
3 2

出力例 1

以下の 4 回の操作で、5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることができます。

マス 1 の石を 1 つマス 2 に移動させる。
マス 2 の石を 1 つマス 3 に移動させる。
マス 4 の石を 1 つマス 5 に移動させる。
マス 1 の石を 1 つマス 2 に移動させる。

また、3 回以下の操作では 5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、4 を出力します。

入力例 2

10 3
1 4 8
4 2 4

出力例 2

-1

どのように操作を行っても 10 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、-1 を出力します。

Score : 300 points

Problem Statement

There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

You can perform the following operation any number of times (possibly zero):

If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

2 \leq N \leq 2 \times 10^{9}
1 \leq M \leq 2 \times 10^{5}
M \leq N
1 \leq X_i \leq N (1 \leq i \leq M)
X_i \neq X_j (1 \leq i < j \leq M)
1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
All input values are integers.

Input

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

N M
X_1 X_2 \ldots X_M
A_1 A_2 \ldots A_M

Output

Print the answer.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

Move one stone from cell 1 to cell 2.
Move one stone from cell 2 to cell 3.
Move one stone from cell 4 to cell 5.
Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

F - Changing Jewels

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はレベル N の赤い宝石を 1 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。

レベル n の赤い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n の青い宝石 X 個」に変換する。
レベル n の青い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n-1 の青い宝石 Y 個」に変換する。

高橋君はレベル 1 の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル 1 の青い宝石を最大何個入手できますか？

制約

1 \leq N \leq 10
1 \leq X \leq 5
1 \leq Y \leq 5
入力される値はすべて整数

入力

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

N X Y

出力

答えを出力せよ。

入力例 1

2 3 4

出力例 1

次のような変換を行うことで、高橋君はレベル 1 の青い宝石を 12 個手に入れることができます。

まず、レベル 2 の赤い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個に変換します。
- 操作後の高橋君は、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個を持っています。
次に、レベル 2 の青い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 1 の青い宝石 4 個に変換します。この変換を 3 回繰り返します。
- 操作後の高橋君は、レベル 1 の赤い宝石 4 個とレベル 1 の青い宝石 12 個を持っています。
これ以上変換を行うことはできません。

12 個より多くレベル 1 の青い宝石を手に入れることはできないので、答えは 12 になります。

入力例 2

1 5 5

出力例 2

高橋君がレベル 1 の青い宝石を 1 個も手に入れられない場合もあります。

入力例 3

10 5 5

出力例 3

3942349900

答えが 32 bit 整数に収まらない場合があることに注意してください。

Score : 300 points

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

1 \leq N \leq 10
1 \leq X \leq 5
1 \leq Y \leq 5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
- After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
- After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

G - 1122 Substring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

正整数からなる（空でも良い）数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
（1122 数列の定義はF問題と共通です。）

\lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1} と X_{2i} は等しい。
各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられるので、A の 連続する部分列 であって、1122 数列であるようなもののうち最長のものの長さを出力してください。

制約

1\leq N \leq 2\times 10^5
1\leq A_i \leq N
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

A の連続する部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。

入力例 1

8
2 3 1 1 2 2 1 1

出力例 1

例えば A の 3 項目から 6 項目までの連続部分列をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。

入力例 2

3
1 2 2

出力例 2

入力例 3

1
1

出力例 3

項数が 0 の列も 1122 数列の条件をみたしていることに注意してください。

Score : 425 points

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem F.)

\lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Constraints

1\leq N \leq 2 \times 10^5
1\leq A_i \leq N
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

Print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Sample Input 1

8
2 3 1 1 2 2 1 1

Sample Output 1

For example, taking the subarray from the 3-rd to 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer (contiguous) subarray that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

3
1 2 2

Sample Output 2

Sample Input 3

1
1

Sample Output 3

Note that a sequence of length 0 also satisfies the conditions for a 1122 sequence.

H - Yacht

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

5 個の 6 面ダイスがあります。どのダイスも各面に書かれた数は A_1,\ldots,A_6 の 6 個であり、各面が出る確率は \frac{1}{6} です。

あなたはこれらのダイスを使って次の手順で 1 人ゲームを行います。

5 個のダイスを全て振り、その結果を見て、好きな個数(0 個でもよい)のダイスをキープする。
キープされていないダイスを全て振り直し、その結果を見て、振り直したダイスのうち好きな個数(0 個でもよい)のダイスを追加でキープする。前のステップでキープしたダイスはキープしたままとなる。
キープされていないダイスを全て振り直し、その結果を見る。
好きな数 X を選ぶ。5 個のダイスのうち X の目が出ているダイスの個数を n として、このゲームの得点は nX 点となる。

ゲームの得点の期待値を最大化するように行動するときの、ゲームの得点の期待値を求めてください。

制約

A_i は 1 以上 100 以下の整数

入力

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

A_1 A_2 A_3 A_4 A_5 A_6

出力

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

入力例 1

1 2 3 4 5 6

出力例 1

14.6588633742

例えばゲームは次のように進行します。（最適な行動とは限りません）

5 個のダイスを全て振り、それぞれ 3,3,1,5,6 の目が出る。3 の目が出た 2 個のダイスをキープする。
キープされていない 3 個のダイスを振り、それぞれ 6,6,2 の目が出る。6 の目が出た 2 個のダイスを追加でキープする。
キープされていない 1 個のダイスを振り、4 の目が出る。
X として 6 を選ぶ。5 個のダイスの出目はそれぞれ 3,3,6,6,4 なので、6 の目が出ているダイスの個数は 2 であり、このゲームの得点は 12 となる。

このケースでは最適に行動した場合の期待値は \frac{143591196865}{9795520512}=14.6588633742\ldots となります。

入力例 2

1 1 1 1 1 1

出力例 2

5.0000000000

ダイスは同じ値が書かれた面を持つことがあります。

入力例 3

31 41 59 26 53 58

出力例 3

159.8253021021

Score : 475 points

Problem Statement

There are five six-sided dice. Each die has the numbers A_1,\ldots,A_6 written on its faces, and each face appears with probability \frac{1}{6}.

You will play a single-player game using these dice with the following procedure:

Roll all five dice, observe the results, and keep any number (possibly zero) of dice.
Re-roll all dice that are not kept, observe the results, and additionally keep any number (possibly zero) of the re-rolled dice. The dice kept in the previous step remain kept.
Re-roll all dice that are not kept and observe the results.
Choose any number X. Let n be the number of dice among the five dice that show X. The score of this game is nX points.

Find the expected value of the game score when you act to maximize the expected value of the game score.

Constraints

A_i is an integer between 1 and 100, inclusive.

Input

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

A_1 A_2 A_3 A_4 A_5 A_6

Output

Print the answer. Your answer will be considered correct if the relative or absolute error from the true value is at most 10^{-5}.

Sample Input 1

1 2 3 4 5 6

Sample Output 1

14.6588633742

For example, the game may proceed as follows (not necessarily optimal):

Roll all five dice and get 3,3,1,5,6. Keep the two dice that show 3.
Re-roll the three dice that are not kept and get 6,6,2. Additionally keep the two dice that show 6.
Re-roll the one die that is not kept and get 4.
Choose X = 6. The dice show 3,3,6,6,4, so the number of dice showing 6 is 2, and the score of this game is 12.

In this case, the expected value when acting optimally is \frac{143591196865}{9795520512}=14.6588633742\ldots.

Sample Input 2

1 1 1 1 1 1

Sample Output 2

5.0000000000

The dice may have faces with the same value written on them.

Sample Input 3

31 41 59 26 53 58

Sample Output 3

159.8253021021

I - Exactly K Steps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点の木が与えられます。頂点には 1, \dots, N の番号が付けられており、i \, (1 \leq i \leq N - 1) 番目の辺は頂点 A_i, B_i を結びます。

この木における頂点 u, v の距離を、頂点 u から頂点 v までの最短パス上にある辺の本数と定義します。

Q 個のクエリが与えられます。i \, (1 \leq i \leq Q) 番目のクエリでは、整数 U_i, K_i が与えられるので、頂点 U_i からの距離がちょうど K_i であるような頂点の番号を任意に一つ出力してください。そのような頂点が存在しない場合は、-1 を出力してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)
与えられるグラフは木
1 \leq Q \leq 2 \times 10^5
1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)
入力は全て整数

入力

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
Q
U_1 K_1
\vdots
U_Q K_Q

出力

Q 行出力せよ。i \, (1 \leq i \leq Q) 行目には、頂点 U_i からの距離がちょうど K_i である頂点が存在するならその一例を、存在しないなら -1 を出力せよ。そのような頂点が複数存在する場合、どれを出力しても正解となる。

入力例 1

出力例 1

4
1
-1

頂点 2 からの距離がちょうど 2 であるのは頂点 4, 5 の二つです。
頂点 5 からの距離がちょうど 3 であるのは頂点 1 のみです。
頂点 3 からの距離がちょうど 3 である頂点は存在しません。

入力例 2

出力例 2

Score : 500 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq N - 1) edge connects Vertices A_i and B_i.

We define the distance between Vertices u and v on this tree by the number of edges in the shortest path from Vertex u to Vertex v.

You are given Q queries. In the i-th (1 \leq i \leq Q) query, given integers U_i and K_i, print the index of any vertex whose distance from Vertex U_i is exactly K_i. If there is no such vertex, print -1.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)
The given graph is a tree.
1 \leq Q \leq 2 \times 10^5
1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
Q
U_1 K_1
\vdots
U_Q K_Q

Output

Print Q lines. The i-th (1 \leq i \leq Q) line should contain the index of any vertex whose distance from Vertex U_i is exactly K_i if such a vertex exists; if not, it should contain -1. If there are multiple such vertices, you may print any of them.

Sample Input 1

Sample Output 1

4
1
-1

Two vertices, Vertices 4 and 5, have a distance exactly 2 from Vertex 2.
Only Vertex 1 has a distance exactly 3 from Vertex 5.
No vertex has a distance exactly 3 from Vertex 3.

Sample Input 2

Sample Output 2