AtCoder Grand Contest 001

A - BBQ Easy

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

高橋君はバーベキューをしようとしています。バーベキューでは 2 本の串にいくつかの具材を刺した串焼きを N 個作る予定です。

串焼きの例

串は 2N 本あり、i 番目の串の長さは L_i です。具材は無限に用意されています。

串を 2 本組にして具材を刺して串焼きにするのですが、2 本の串のうち短い方の長さを x とすると、串焼きには最大 x 個の具材を刺すことができます。

うまく串を組み合わせたとき、N 個の串焼きに刺すことのできる具材の個数の和の最大値はいくらになるでしょうか？

制約

1≦N≦100
1≦L_i≦100
L_i は整数である。

入力

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

N
L_1 L_2 ... L_{2N}

出力

N 個の串焼きに刺すことのできる具材の個数の和の最大値を出力せよ。

入力例 1

2
1 3 1 2

出力例 1

1 番目と 3 番目、2 番目と 4 番目の串を組にすると、それぞれの串焼きには 1 個、 2 個の具材を刺すことができ、合計 3 個の具材を刺すことができます。

入力例 2

5
100 1 2 3 14 15 58 58 58 29

出力例 2

Score : 200 points

Problem Statement

Snuke is having a barbeque party.

At the party, he will make N servings of Skewer Meal.

Example of a serving of Skewer Meal

He has a stock of 2N skewers, all of which will be used in Skewer Meal. The length of the i-th skewer is L_i. Also, he has an infinite supply of ingredients.

To make a serving of Skewer Meal, he picks 2 skewers and threads ingredients onto those skewers. Let the length of the shorter skewer be x, then the serving can hold the maximum of x ingredients.

What is the maximum total number of ingredients that his N servings of Skewer Meal can hold, if he uses the skewers optimally?

Constraints

1≦N≦100
1≦L_i≦100
For each i, L_i is an integer.

Input

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

N
L_1 L_2 ... L_{2N}

Output

Print the maximum total number of ingredients that Snuke's N servings of Skewer Meal can hold.

Sample Input 1

2
1 3 1 2

Sample Output 1

If he makes a serving using the first and third skewers, and another using the second and fourth skewers, each serving will hold 1 and 2 ingredients, for the total of 3.

Sample Input 2

5
100 1 2 3 14 15 58 58 58 29

Sample Output 2

B - Mysterious Light

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

高橋君は 1 辺の長さが N の 3 枚の鏡を正三角形状に組み合わせました。三角形の頂点をそれぞれ a, b, c とします。

高橋君は、辺 ab 上の頂点 a から X の点から、辺 bc と平行に不思議な光を発射しました。不思議な光は、普通の光と同じように真っすぐ進み、鏡に当たると反射するのですが、不思議な光がすでに通った点に当たったときにも反射をします。例えば、N = 5, X = 2 のとき、不思議な光の軌跡は図の黄色い矢印のようになります。

このように不思議な光を発射した時、不思議な光は必ず発射した点に戻ってくることが証明できます。このとき、光の軌跡の長さが全体でいくらになるかを求めて下さい。

制約

2≦N≦10^{12}
1≦X≦N-1
N と X はいずれも整数である。

部分点

N≦1000 を満たすデータセットに正解した場合は、300 点が与えられる。
追加制約のないデータセットに正解した場合は、上記とは別に 200 点が与えられる。

入力

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

N X

出力

光の軌跡全体の長さを出力せよ。

入力例 1

5 2

出力例 1

問題文中の図のとおりです。光の軌跡の長さは全体で 2+3+2+2+1+1+1 = 12 となります。

Score : 500 points

Problem Statement

Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of Mysterious Light.

Three mirrors of length N are set so that they form an equilateral triangle. Let the vertices of the triangle be a, b and c.

Inside the triangle, the rifle is placed at the point p on segment ab such that ap = X. (The size of the rifle is negligible.) Now, the rifle is about to fire a ray of Mysterious Light in the direction of bc.

The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as "ordinary" light. There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror! When the ray comes back to the rifle, the ray will be absorbed.

The following image shows the ray's trajectory where N = 5 and X = 2.

It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of N and X. Find the total length of the ray's trajectory.

Constraints

2≦N≦10^{12}
1≦X≦N-1
N and X are integers.

Partial Points

300 points will be awarded for passing the test set satisfying N≦1000.
Another 200 points will be awarded for passing the test set without additional constraints.

Input

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

N X

Output

Print the total length of the ray's trajectory.

Sample Input 1

5 2

Sample Output 1

Refer to the image in the Problem Statement section. The total length of the trajectory is 2+3+2+2+1+1+1 = 12.

C - Shorten Diameter

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

N 頂点の木があり、頂点には 1 ～ N の番号がついています。N - 1 本の辺について、i (1≦i≦N-1) 本目の辺は頂点 A_i と頂点 B_i を繋いでいます。

この木の直径を K 以下にするために削除する必要のある頂点数の最小値を求めてください。ただし、頂点を削除した後のグラフは連結になっていなければなりません。

木の直径とは、2 つの頂点間の距離の最大値のことを指します。2 つの頂点間の距離とは、2 つの頂点を結ぶパスに含まれる辺の本数を指します。

制約

2≦N≦2000
1≦K≦N-1
1≦A_i≦N, 1≦B_i≦N
与えられるグラフは木である。

入力

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

N K
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}

出力

直径を K 以下にするために削除する必要のある頂点数の最小値を出力せよ。

入力例 1

出力例 1

木の構造は図のとおりです。頂点 5,6 を削除すると直径を 2 に出来ます。

入力例 2

出力例 2

すでに直径が K 以下なので、頂点を削除する必要はありません。

Score : 600 points

Problem Statement

Given an undirected tree, let the distance between vertices u and v be the number of edges on the simple path from u to v. The diameter of a tree is the maximum among the distances between any two vertices. We will call a tree good if and only if its diameter is at most K.

You are given an undirected tree with N vertices numbered 1 through N. For each i (1≦i≦N-1), there is an edge connecting vertices A_i and B_i.

You want to remove zero or more vertices from the tree, so that the resulting tree is good. When a vertex is removed, all incident edges will also be removed. The resulting graph must be connected.

Find the minimum number of vertices that you need to remove in order to produce a good tree.

Constraints

2≦N≦2000
1≦K≦N-1
1≦A_i≦N, 1≦B_i≦N
The graph defined by A_i and B_i is a tree.

Input

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

N K
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}

Output

Print the minimum number of vertices that you need to remove in order to produce a good tree.

Sample Input 1

Sample Output 1

The tree is shown below. Removing vertices 5 and 6 will result in a good tree with the diameter of 2.

Sample Input 2

Sample Output 2

Since the given tree is already good, you do not need to remove any vertex.

D - Arrays and Palindrome

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

高橋君のお母さんは、高橋君の誕生日に数列 a, b をプレゼントしました。数列 a, b は以下の性質をすべて満たしていたため、高橋君はとても喜びました。

数列 a に含まれる数の総和は N である。
数列 b に含まれる数の総和は N である。
数列 a, b に含まれる数はすべて正の整数である。
以下の条件を 2 つとも満たす長さ N の文字列は、必ずすべての文字が同じである。
- 先頭の a_1 文字、続く a_2 文字、さらに続く a_3 文字 ... はすべて回文である。
- 先頭の b_1 文字、続く b_2 文字、さらに続く b_3 文字 ... はすべて回文である。

しかしある日、高橋君は数列 a, b を両方ともなくしてしまいました。幸運なことに、高橋君は数列 a が長さ M の数列 A の並び替えであったことを覚えています。

高橋君のお母さんは高橋君を喜ばせるために、数列 a, b として考えられるものを高橋君にもう一度プレゼントしようと考えました。

制約

1≦N≦10^5
1≦M≦100
1≦A_i≦10^5
A_i の総和は N である。

入力

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

N M
A_1 A_2 ... A_M

出力

数列 a, b として考えられるものがある場合、数列 a、数列 b の長さ、数列 b を順に出力せよ。ただし、高橋君の勘違いなどの理由で数列 a, b として考えられるものが存在しない場合がある。その場合は代わりに Impossible と出力せよ。

入力例 1

3 2
2 1

出力例 1

1 2
1
3

入力例 2

6 1
6

出力例 2

6
3
1 2 3

入力例 3

55 10
1 2 3 4 5 6 7 8 9 10

出力例 3

Impossible

Score : 1000 points

Problem Statement

Snuke got a present from his mother on his birthday. The present was a pair of two sequences a and b, consisting of positive integers. They satisfied all of the following properties:

The sum of all elements of a is N.
The sum of all elements of b is N.
Any string of length N that satisfies the following two conditions (1) and (2) will also satisfy the condition (3).

(1) Any of the following forms a palindrome: the first a_1 letters, the following a_2 letters, the following a_3 letters and so on.
(2) Any of the following forms a palindrome: the first b_1 letters, the following b_2 letters, the following b_3 letters and so on.
(3) All N letters are the same.

He was happy, until one day he lost both of the sequences. Now, he only remembers that the sequence a was a permutation of another sequence A of length M.

To bring him happiness again, his mother has decided to give him another pair of sequences a and b that satisfies his favorite properties and is consistent with his memory.

Constraints

1≦N≦10^5
1≦M≦100
1≦A_i≦10^5
The sum of all A_i equals N.

Input

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

N M
A_1 A_2 ... A_M

Output

If there exists a pair of sequences a and b that satisfies the properties and is consistent with Snuke's memory, print three lines. The first line must contain the sequence a, the second line must contain the length of the sequence b, and the third line must contain the sequence b.

If such a pair does not exist (because Snuke's memory is wrong or some other reason), print a single line containing the word Impossible (case-sensitive).

Sample Input 1

3 2
2 1

Sample Output 1

1 2
1
3

Sample Input 2

6 1
6

Sample Output 2

6
3
1 2 3

Sample Input 3

55 10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

Impossible

E - BBQ Hard

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1400 点

問題文

高橋君はバーベキューをしようとしています。バーベキューでは 2 本の串にいくつかの具材を刺した串焼きを 1 個作る予定です。

串焼きセットが N 個あり、i 番目のセットには串が 1 本、肉が A_i 個、野菜が B_i 個入っています。

セットを 2 個選び、セット 2 つに含まれる全ての具材を好きな順番で串 2 本に刺すことを考えます。このとき、作ることの出来る串焼きは何通り考えられるでしょうか？ただし、串どうしは区別でき、肉どうしや野菜どうしは区別できないものとします。答えは非常に大きな数になる可能性があるので、10^9+7 で割った余りを求めてください。

制約

2≦N≦200,000
1≦A_i≦2000, 1≦B_i≦2000

入力

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

N
A_1 B_1
A_2 B_2
:
A_N B_N

出力

作ることの出来る串焼きの種類数を 10^9+7 で割った余りを出力せよ。

入力例 1

出力例 1

図のような 26 通りの串焼きを作ることが出来ます。灰色の棒は串を表しており、串に書かれた数はその串が含まれていたセットの番号を表しています。また、茶色の長方形は肉、緑色の長方形は野菜を表しています。

Score : 1400 points

Problem Statement

Snuke is having another barbeque party.

This time, he will make one serving of Skewer Meal.

He has a stock of N Skewer Meal Packs. The i-th Skewer Meal Pack contains one skewer, A_i pieces of beef and B_i pieces of green pepper. All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable.

To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper. (Remaining Skewer Meal Packs will not be used.) Then, all those pieces of food are threaded onto both skewers, one by one, in any order.

(See the image in the Sample section for better understanding.)

In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different. Since this number can be extremely large, find it modulo 10^9+7.

Constraints

2≦N≦200,000
1≦A_i≦2000, 1≦B_i≦2000

Input

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

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo 10^9+7.

Sample Input 1

Sample Output 1

The 26 ways of making a Skewer Meal are shown below. Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer. Brown and green rectangles represent pieces of beef and green pepper, respectively.

F - Wide Swap

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 2000 点

問題文

長さ N の、1 ～ N をちょうど 1 つずつ含む数列 P_1 ... P_N が与えられます。

あなたはこの数列に対し、以下のような操作を何度でも行えます。

整数 i,j (1 ≦ i < j ≦ N) を選ぶ。
P_i と P_j の値を入れ替える。
ただしこのとき、j - i ≧ K かつ |P_i - P_j| = 1 を満たしていなければならない。

このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

制約

2≦N≦500,000
1≦K≦N-1
P は 1, 2, ..., N の順列である。

入力

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

N K
P_1 P_2 ... P_N

出力

問題文中の操作によって作ることのできる辞書順最小の数列を出力せよ。

入力例 1

4 2
4 2 3 1

出力例 1

以下のような手順で操作を行えば良いです。

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

入力例 2

5 1
5 4 3 2 1

出力例 2

入力例 3

8 3
4 5 7 8 3 1 2 6

出力例 3

Score : 2000 points

Problem Statement

You are given a permutation P_1 ... P_N of the set {1, 2, ..., N}.

You can apply the following operation to this permutation, any number of times (possibly zero):

Choose two indices i,j (1 ≦ i < j ≦ N), such that j - i ≧ K and |P_i - P_j| = 1. Then, swap the values of P_i and P_j.

Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

Constraints

2≦N≦500,000
1≦K≦N-1
P is a permutation of the set {1, 2, ..., N}.

Input

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

N K
P_1 P_2 ... P_N

Output

Print the lexicographically smallest permutation that can be obtained.

Sample Input 1

4 2
4 2 3 1

Sample Output 1

One possible way to obtain the lexicographically smallest permutation is shown below:

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

Sample Input 2

5 1
5 4 3 2 1

Sample Output 2

Sample Input 3

8 3
4 5 7 8 3 1 2 6

Sample Output 3