AtCoder Regular Contest 152

A - Seat Occupation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

L 個の椅子が左右一列に並んでおり、これから N 組の人が訪れて、順に座っていきます。ただし、各組は 1 人組または 2 人組であり、i 番目には a_i 人組が訪れます。また、訪れる人数の合計は L に等しいです。

それぞれの組は、椅子の列の中でまだ人が座っていない部分のうち、組の全員が連続して座れるところをランダムに選び、その部分を占有して座ります。ただし、組の全員が連続して座れる場所が無い場合は、座ることができずに帰ってしまいます。

このとき、「誰も帰らずに N 組全員が座ることができる」と確実に言えるかどうか判定してください。

制約

1\leq N\leq 2\times 10^5
1\leq a_i\leq 2
L=a_1 +a_2 +\ldots +a_N
入力される値はすべて整数である

入力

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

N L
a_1 a_2 \ldots a_N

出力

「誰も帰らずに N 組全員が座ることができる」と確実に言える場合は Yes 、そうでない場合は No を出力せよ。

入力例 1

2 4
2 2

出力例 1

No

椅子に左から 1,2,3,4 と番号がついているとします。最初の 2 人組が椅子 2,3 に座った場合、後から来る 2 人組は座ることができずに帰ってしまいます。したがって、全員が座ることができない場合がありますので、No と答えてください。

入力例 2

3 4
1 2 1

出力例 2

Yes

どのような座り方を考えても、全員が確実に椅子に座ることができます。

Score : 400 points

Problem Statement

There is a row of L chairs. Now, N groups of people will come and take seats in order. Each group consists of one or two people, and the i-th group to come consists of a_i people. The total number of people equals L.

Each group will randomly choose unoccupied chairs where all group members can sit consecutively, and occupy those chairs. However, if there are not enough consecutive unoccupied chairs, they will leave without taking seats.

Determine whether it is guaranteed that all N groups can take seats.

Constraints

1\leq N\leq 2\times 10^5
1\leq a_i\leq 2
L=a_1 +a_2 +\ldots +a_N
All values in the input are integers.

Input

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

N L
a_1 a_2 \ldots a_N

Output

If it is guaranteed that all N groups can take seats, print Yes; otherwise, print No.

Sample Input 1

2 4
2 2

Sample Output 1

No

Let us number the chairs 1, 2, 3, 4 from left to right. If the first group of two people takes chairs 2 and 3, the next group of two people cannot take seats and will leave. Thus, it is not guaranteed that all N groups can take seats, so you should print No.

Sample Input 2

3 4
1 2 1

Sample Output 2

Yes

No matter what chairs they choose, everyone can always take a seat.

B - Pass on Path

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ L の細長い一直線の道が東西に伸びており、この道を 2 人の旅人が訪れます。この道には N 個の休憩所があり、i 番目の休憩所は、道の西端から a_i の地点にあります（ただし、どの休憩所も道の端には存在しません）。この道はとても細いため、休憩所以外の地点で 2 人がすれ違ったり、横に並んで歩いたりすることはできません。

2 人の旅人は、この道で次のような旅をします。

時刻 0 に、それぞれ好きな休憩所を選んで出発点とする（ 2 人が同じ休憩所を選んでもよい）。その後、それぞれ道の両端を訪れたあと、自身の出発点に戻る。

2 人は、毎秒 1 以下の速さで道を歩くか、休憩所で休憩することができます。休憩所以外の地点ですれ違わない限り、旅の途中いつでも向きを変えることは可能です。両者が道の両端を訪れて出発点に戻ってくるまで、最短で何秒かかるでしょうか。ただし、この問題の制約下では答えが整数になることが証明できます。

制約

1 \leq N \leq 2 \times 10^5
1 \leq L \leq 10^9
0 < a_1 < a_2 < \ldots < a_N < L
入力される値はすべて整数である

入力

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

N L
a_1 a_2 \ldots a_N

出力

答えを整数で出力せよ。

入力例 1

2 6
2 5

出力例 1

2 人の旅人を A、B とします。また、以下では i 番目の休憩所を単に休憩所 i と呼びます。例えば、2 人は以下のような旅をすることができます。

最初に A が休憩所 1 から東側に、B が休憩所 2 から東側に速さ 1 で歩き始め、両者とも東端→西端の順に訪れることにします。すると、B は 2 秒後に東端を訪れて休憩所 2 に戻って来ることができますが、A はまだ休憩所 1 と 2 の間です。ここで B が 1 秒休憩すると、A も休憩所 2 にたどり着き、すれ違いが可能になります。

その後、再び両者が速さ 1 で歩き続け、A が休憩所 1 で 2 秒だけ休憩した場合、 B は出発から 13 秒後、A は 14 秒後に元の休憩所に戻り、旅を終えることができます。

実はこれは最善の方法の 1 つであり、答えは 14 となります。

入力例 2

2 3
1 2

出力例 2

この場合は、適切な方法を取ると、両者が休憩することなく速さ 1 で歩き続けることができます。

Score : 500 points

Problem Statement

There is a narrow straight road of length L stretching east to west. Two travelers will visit this road. Along the road, there are N rest areas. The distance from the west end of the road to the i-th rest area is a_i (no rest area is at either end of the road). The road is so narrow that the two travelers cannot pass each other or walk side by side except at the rest areas.

The two travelers will take a trip along the road as follows.

At time 0, each traveler starts at a rest area of their choice (the two may start at the same rest area). Then, each visits both ends of the road, and returns to their own starting rest area.

During the trip, they can walk along the road at a speed of at most 1, or rest at a rest area. As long as they only pass each other at the rest areas, it is always allowed to change direction. What is the smallest number of seconds needed for both travelers to visit both ends of the road and return to their starting rest areas? It can be proved that the answer is always an integer under the Constraints of this problem.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L \leq 10^9
0 < a_1 < a_2 < \ldots < a_N < L
All values in the input are integers.

Input

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

N L
a_1 a_2 \ldots a_N

Output

Print the answer as an integer.

Sample Input 1

2 6
2 5

Sample Output 1

Let us name the travelers A and B. Also, call the i-th rest area simply rest area i. Here is a possible trip.

At the beginning, A starts at rest area 1 walking to the east, and B starts at rest area 2 walking to the east, both at a speed of 1, planning to visit the east end first and then the west end. Then, two seconds later, B is back at rest area 2 after visiting the east end, but A is still halfway between rest areas 1 and 2. If B rests here for one second, A will also arrive at rest area 2, where they can pass each other.

Afterward, if they continue to walk at a speed of 1 and A rests at rest area 1 for two seconds, B will be back at the starting rest area at time 13, and A will be back at time 14, completing the trip.

This trip turns out to be optimal: the answer is 14.

Sample Input 2

2 3
1 2

Sample Output 2

In this case, an optimal trip will allow both travelers to keep walking at a speed of 1 without resting.

C - Pivot

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 項からなる数列 a_1,a_2,\ldots,a_N があります。あなたはこれから、この数列に以下の操作を好きな回数行うことができます。（1 回も行わなくてもよいです。）

その時点の数列から項を 1 つ選び、その値を s とする。次に、全ての 1\leq i\leq N に対して、a_i を 2s-a_i で置き換える。ただし、この操作によって、数列に負の値を持つ項が生じてはならない。

あなたは、数列の項の最大値をできるだけ小さくしたいと考えています。適切に操作を行った場合の、数列の項の最大値はいくつになるでしょうか。

制約

2 \leq N \leq 2 \times 10^5
1 \leq a_1 < a_2 < \ldots < a_N \leq 10^9
入力される値はすべて整数である

入力

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

N
a_1 a_2 \ldots a_N

出力

答えを整数で出力せよ。

入力例 1

3
1 3 6

出力例 1

s=3 として操作を行うと、数列は (5,3,0) になります。このとき最大値は 5 です。数列に負の項が生じてはいけないという条件の下で、これ以上数列の項の最大値を小さくすることはできませんので、5 と答えてください。

入力例 2

5
400 500 600 700 800

出力例 2

s=400 として操作を一度行うほか、s=500 として操作を行った後、s=300 としてもう一度操作を行うなどの方法が考えられます。

Score : 600 points

Problem Statement

We have a sequence of N terms: a_1,a_2,\ldots,a_N. You can perform the following operation on this sequence any number of times (possibly zero).

Choose a term of the sequence at that point, and let s be its value. Then, for every 1\leq i\leq N, replace a_i with 2s-a_i. However, this operation may not be performed in a way that produces a term with a negative value.

You want to make the greatest value among the terms of the sequence as small as possible. What will this value be after an optimal sequence of operations for this objective?

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq a_1 < a_2 < \ldots < a_N \leq 10^9
All values in the input 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 answer.

Sample Input 1

3
1 3 6

Sample Output 1

If you perform the operation with s=3, the sequence becomes (5,3,0). The greatest value here is 5. Under the condition that there may not be a term with a negative value, the greatest value among the terms of the sequence cannot be made smaller, so you should print 5.

Sample Input 2

5
400 500 600 700 800

Sample Output 2

To obtain this result, perform the operation once with s=400, or perform it with s=500 and then with s=300, for instance.

D - Halftree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

頂点に 0 から N-1 までの番号がついた N 頂点の無向グラフがあり、はじめ、辺はありません。このグラフに、あなたは好きなように辺を追加することができます。そして、あなたが辺をすべて追加し終えた後に、与えられる K を用いて以下の操作がちょうど 1 回行われます。

あなたが追加した各辺について、両端の頂点を u,v とするとき、 2 頂点 (u+K) \mathrm{mod} N と (v+K) \mathrm{mod} N の間に辺が追加される。ただし、この 2 頂点間にもともと辺が存在する場合も新しく辺が追加されるため、その場合は操作後には多重辺となる。

与えられた N,K に対して、操作後のグラフが木となるようにするとき、あなたが追加するべき辺の組を求めてください。そのような辺の組が存在しない場合はそのことを指摘してください。

制約

2\leq N\leq 2\times 10^5
1\leq K\leq N-1
入力される値はすべて整数である

入力

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

N K

出力

題意を満たす辺の組が存在する場合、辺の数を M、 i 番目の辺が結ぶ 2 頂点を a_i,b_i として、以下の形式で出力せよ。ただし、 0\leq M\leq N でなければならず、全て整数で出力せよ。出力される辺や頂点の順序は問わない。

M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

解が複数存在する場合、どれを出力しても正解とみなされる。

題意を満たす辺の組が存在しない場合、-1 と出力せよ。

入力例 1

5 2

出力例 1

2
2 3
2 4

操作を行うと、辺 4-0 と 4-1 が追加されます。したがって、木が生成されますので、これは正当な出力の 1 つとなります。

入力例 2

2 1

出力例 2

-1

操作後のグラフが木となるような方法が存在しません。

入力例 3

7 1

出力例 3

Score : 700 points

Problem Statement

We have an undirected graph with N vertices numbered 0 through N-1 and no edges at first. You may add edges to this graph as you like. When you are done with adding edges, the following operation will be performed once using a given integer K.

For each edge you have added, let u and v be its endpoints, and an edge will be added between two vertices (u+K) \mathrm{mod} N and (v+K) \mathrm{mod} N. This edge will be added even if there is already an edge between these vertices, resulting in multi-edges.

For the given N and K, find a set of edges that you should add so that the graph will be a tree after the operation. If there is no such set of edges, indicate that fact.

Constraints

2\leq N\leq 2\times 10^5
1\leq K\leq N-1
All values in the input are integers.

Input

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

N K

Output

If there is a set of edges that satisfies the requirement, let M be the number of edges, and a_i and b_i be the two vertices connected by the i-th edge, and print a solution in the following format. Here, 0\leq M\leq N must hold, and all values must be integers. The edges may be printed in any order, as well as the endpoints of an edge.

M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

If multiple solutions exist, any of them will be accepted.

If no set of edges satisfies the requirement, print -1.

Sample Input 1

5 2

Sample Output 1

2
2 3
2 4

The operation will add the edges 4-0 and 4-1. Then, the graph will be a tree, so this is a legitimate output.

Sample Input 2

2 1

Sample Output 2

-1

There is no way to have a tree after the operation.

Sample Input 3

7 1

Sample Output 3

E - Xor Annihilation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

数直線上の x=1,2,3,...,2^N-1 の位置に 2^N-1 個のボールが並んでおり、x=i にあるボールは w_i の重みを持っています。ただし、w_1, w_2,...,w_{2^N-1} は 1 から 2^N-1 までの整数を並び替えた数列です。さらに、あなたは 2^N-1 以下の負でない整数 Z を 1 つ選び、座標 x=\pm 100^{100^{100}} にそれぞれ Z の重みを固定します。その後、各ボールは次の規則にしたがって、一斉に運動を始めます。

各時点で、ボールの存在している座標より真に右側にある座標・ボールの重みの総 \mathrm{XOR} を R、真に左側にある座標・ボールの重みの総 \mathrm{XOR} を L とすると、このボールは R>L であれば右側に、L>R であれば左側に毎秒 1 の速さで動き、L=R であれば静止する。
左右から来たボールが同じ座標に到達したときなど、同じ座標に同時に複数のボールが存在した場合、これらのボールは合体し、その重みは合体前の重みの総 \mathrm{XOR} となる。

このとき、100^{100} 秒以内に全てのボールが静止するような Z はいくつあるでしょうか。

\mathrm{XOR} とは

非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。

A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

2\leq N\leq 18
1\leq w_i\leq 2^N-1
i\neq j のとき w_i\neq w_j
入力される値はすべて整数である

入力

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

N
w_1 w_2 \ldots w_{2^N-1}

出力

答えを整数で出力せよ。

入力例 1

2
1 2 3

出力例 1

i の重みを持つボールを単に i と呼びます。

例えば Z=0 とした場合、はじめ 1 と 2 は右向きに、3 は左向きに動きます。すると 2 と 3 がぶつかって合体し、この瞬間から左向きに動き始めます。そののち、1 から 3 まで全てのボールが合体した瞬間に合体後のボールは静止します。したがって、Z=0 は条件を満たします。

また、Z=3 とした場合、1 と 2 は左向き、3 は右向きに、固定した重みに向かって 100^{100^{100}} 秒程度動き続けることになります。したがって、Z=3 は条件を満たしません。

実は Z=0 のみが条件を満たすため、1 と答えてください。

入力例 2

3
7 1 2 3 4 5 6

出力例 2

Score : 800 points

Problem Statement

On a number line, there are 2^N-1 balls at the coordinates x=1,2,3,...,2^N-1, and the ball at x=i has a weight of w_i. Here, w_1, w_2,...,w_{2^N-1} is a permutation of the integers from 1 through 2^N-1. You will choose a non-negative integer Z at most 2^N-1 and attach a weight of Z at each of the coordinates x=\pm 100^{100^{100}}. Then, the balls will simultaneously start moving as follows.

At each time, let R be the total \mathrm{XOR} of the weights of the balls and attached weights that are strictly to the right of the coordinate of a ball, and L be the total \mathrm{XOR} of the weights of the balls and attached weights that are strictly to the left. If R>L, the ball moves to the right at a speed of 1 per second; if L>R, the ball moves to the left at a speed of 1 per second; if L=R, the ball stands still.
If multiple balls exist at the same coordinate (when, for instance, two balls coming from the left and right reach there), the balls combine into one whose weight is the total \mathrm{XOR} of their former weights.

For how many values of Z will all balls come to rest within 100^{100} seconds?

What is \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows.

When A \oplus B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.

For instance, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.

Constraints

2\leq N\leq 18
1\leq w_i\leq 2^N-1
w_i\neq w_j if i\neq j.
All values in the input are integers.

Input

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

N
w_1 w_2 \ldots w_{2^N-1}

Output

Print the answer as an integer.

Sample Input 1

2
1 2 3

Sample Output 1

Let us call a ball with a weight of i simply i.

If Z=0, for instance, 1 and 2 first move to the right, and 3 moves to the left. Then, the moment 2 and 3 collide and combine into one ball, it starts moving to the left. Afterward, the moment all balls from 1 to 3 combine into one ball, it stands still. Thus, Z=0 satisfies the condition.

On the other hand, if Z=3, then 1 and 2 keep moving to the left, and 3 keeps moving to the right, toward the attached weights for approximately 100^{100^{100}} seconds. Thus, Z=3 does not satisfy the condition.

It turns out that Z=0 is the only value that satisfies the condition, so you should print 1.

Sample Input 2

3
7 1 2 3 4 5 6

Sample Output 2

F - Attraction on Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

頂点に 1 から N までの番号がついた N 頂点の木が与えられます。この木の i 番目の辺は、2 頂点 a_i,b_i を結んでいます (1\leq i\leq N-1) 。

はじめ、頂点 1 に駒が置いてあり、あなたはこれから、以下の操作をちょうど N 回行います。

その時点で駒が置かれておらず、かつ今までの操作で一度も選択されていない頂点を 1 つ選び、駒を選んだ頂点の方向に 1 つ動かす。

N 回の操作を終えた後、駒が頂点 N に置いてあるような手順を「よい手順」と呼びます。さらに、よい手順のうち、手順中に駒が置かれたことのある頂点数（頂点 1,N を含む）が最小となるものを「最良の手順」と呼びます。

最良の手順において、手順中に駒が置かれたことのある頂点の個数を求めてください。ただし、よい手順が存在しないときは -1 と答えてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq a_i,b_i \leq N
入力される値はすべて整数である
与えられるグラフは木である

入力

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

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

出力

答えを整数で出力せよ。

入力例 1

出力例 1

頂点 3,1,2,4 の順で選択すると、駒の位置は開始時から順に 1 → 2 → 1 → 2 → 4 となり、これが最良の手順の一例です。

入力例 2

出力例 2

-1

よい手順が存在しません。

入力例 3

出力例 3

Score : 1000 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge connects two vertices a_i and b_i (1\leq i\leq N-1).

Initially, a piece is placed at vertex 1. You will perform the following operation exactly N times.

Choose a vertex that is not occupied by the piece at that moment and is never chosen in the previous operations, and move the piece one vertex toward the chosen vertex.

A way to perform the operation N times is called a good procedure if the piece ends up at vertex N. Additionally, a good procedure is called an ideal procedure if the number of vertices visited by the piece at least once during the procedure (including vertices 1 and N) is the minimum possible.

Find the number of vertices visited by the piece at least once during an ideal procedure. If there is no good procedure, print -1 instead.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq a_i,b_i \leq N
All values in the input are integers.
The given graph is a tree.

Input

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

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

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

If you choose vertices 3, 1, 2, 4 in this order, the piece will go along the path 1 → 2 → 1 → 2 → 4. This is an ideal procedure.

Sample Input 2

Sample Output 2

-1

There is no good procedure.

Sample Input 3