AtCoder Weekday Contest 0167 Beta

A - Mountain Summit

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は山道を歩きながら、道沿いに並んだ N 個の地点で順に標高を記録しました。地点 i（1 \leq i \leq N）の標高は A_i です。

ある地点 i（ただし 1 < i < N）が

A_{i-1} < A_i かつ A_i > A_{i+1}

を満たすとき、すなわち両隣の地点よりも標高が厳密に高いとき、その地点を「山頂」と呼びます。

標高データに含まれる「山頂」の個数を求めてください。

制約

3 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9（1 \leq i \leq N）
入力はすべて整数である

入力

N
A_1 A_2 \cdots A_N

1 行目には、地点の数を表す整数 N が与えられる。
2 行目には、各地点の標高を表す N 個の整数 A_1, A_2, \ldots, A_N が空白区切りで与えられる。

出力

「山頂」である地点の個数を 1 行に出力してください。

入力例 1

5
1 3 2 4 1

出力例 1

入力例 2

4
1 2 3 4

出力例 2

入力例 3

12
2 5 1 4 3 6 6 5 8 2 7 1

出力例 3

入力例 4

25
0 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 0

出力例 4

入力例 5

3
0 1000000000 0

出力例 5

Score : 233 pts

Problem Statement

Takahashi walked along a mountain trail and recorded the elevation at N points lined up along the path, in order. The elevation at point i (1 \leq i \leq N) is A_i.

A point i (where 1 < i < N) is called a "peak" if it satisfies

A_{i-1} < A_i and A_i > A_{i+1},

that is, if its elevation is strictly higher than both of its neighboring points.

Find the number of "peaks" contained in the elevation data.

Constraints

3 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9 (1 \leq i \leq N)
All input values are integers

Input

N
A_1 A_2 \cdots A_N

The first line contains an integer N, representing the number of points.
The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the elevation at each point.

Output

Print the number of points that are "peaks" on a single line.

Sample Input 1

5
1 3 2 4 1

Sample Output 1

Sample Input 2

4
1 2 3 4

Sample Output 2

Sample Input 3

12
2 5 1 4 3 6 6 5 8 2 7 1

Sample Output 3

Sample Input 4

25
0 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 0

Sample Output 4

Sample Input 5

3
0 1000000000 0

Sample Output 5

B - Network Construction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は N 台のコンピュータを管理しています。各コンピュータには番号 1 から N が付けられており、コンピュータ i にはネットワークポートがちょうど A_i 個あります。

高橋君はこれらのコンピュータの中から 1 台以上を選び（同じコンピュータを複数回選ぶことはできません）、選んだコンピュータ同士をケーブルで接続してネットワークを構築したいと考えています。ケーブルによる接続は、以下のルールに従います。

ケーブル 1 本は、選んだコンピュータのうち異なる 2 台のポートを 1 つずつ使って接続する。
同じ 2 台のコンピュータ間に複数本のケーブルを接続することはできない。

次の条件をすべて満たすようにネットワークを構築できるか判定してください。

木構造条件： 選んだコンピュータ全体が木構造をなす。すなわち、選んだコンピュータが k 台（k \geq 2）の場合、ケーブルがちょうど k - 1 本あり、選んだ任意の 2 台のコンピュータ間にケーブルをたどる経路がちょうど 1 通り存在する。選んだコンピュータが 1 台のみの場合は、ケーブルが 0 本でこの条件を満たすとみなす。
ポート使い切り条件： 選んだ各コンピュータについて、そのすべてのポートが使われている。すなわち、選んだコンピュータ i に接続されるケーブルの本数がちょうど A_i 本である（A_i = 0 のコンピュータを 1 台だけ選んだ場合、ケーブル 0 本で条件を満たす）。

条件を満たすネットワークを構築できるなら Yes を、できないなら No を出力してください。

制約

1 \leq N \leq 10^6
0 \leq A_i \leq 10^9
入力はすべて整数である

入力

N
A_1 A_2 \ldots A_N

1 行目には、コンピュータの台数を表す整数 N が与えられる。
2 行目には、各コンピュータのポート数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

条件を満たすネットワークを構築できるなら Yes を、できないなら No を 1 行に出力せよ。

入力例 1

3
1 2 1

出力例 1

Yes

入力例 2

2
2 2

出力例 2

No

入力例 3

10
3 1 1 1 7 4 2 2 5 9

出力例 3

Yes

入力例 4

40
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 4

Yes

入力例 5

1
0

出力例 5

Yes

Score : 333 pts

Problem Statement

Takahashi manages N computers. Each computer is numbered from 1 to N, and computer i has exactly A_i network ports.

Takahashi wants to select one or more of these computers (each computer can be selected at most once) and connect the selected computers with cables to build a network. The cable connections must follow these rules:

One cable connects two distinct selected computers, using one port from each.
Multiple cables cannot be connected between the same pair of computers.

Determine whether it is possible to build a network satisfying all of the following conditions:

Tree structure condition: The selected computers form a tree structure. That is, if k computers are selected (k \geq 2), there are exactly k - 1 cables, and between any two selected computers there exists exactly one path following cables. If only one computer is selected, this condition is considered satisfied with 0 cables.
Port exhaustion condition: For each selected computer, all of its ports are used. That is, the number of cables connected to selected computer i is exactly A_i (if only one computer with A_i = 0 is selected, the condition is satisfied with 0 cables).

If a network satisfying the conditions can be constructed, output Yes; otherwise, output No.

Constraints

1 \leq N \leq 10^6
0 \leq A_i \leq 10^9
All inputs are integers

Input

N
A_1 A_2 \ldots A_N

The first line contains an integer N representing the number of computers.
The second line contains the number of ports for each computer A_1, A_2, \ldots, A_N, separated by spaces.

Output

If a network satisfying the conditions can be constructed, output Yes; otherwise, output No on a single line.

Sample Input 1

3
1 2 1

Sample Output 1

Yes

Sample Input 2

2
2 2

Sample Output 2

No

Sample Input 3

10
3 1 1 1 7 4 2 2 5 9

Sample Output 3

Yes

Sample Input 4

40
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 4

Yes

Sample Input 5

1
0

Sample Output 5

Yes

C - Planting the Flower Bed

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は公園の花壇の管理を任されています。花壇には N 株の花を植える必要があります。

花壇には M 個の植え付けポイントが一直線上に並んでおり、左から順にポイント 1 、ポイント 2 、...、ポイント M と番号が付けられています。ポイント i とポイント i+1 の間の距離は D_i メートルです。各ポイントには最大 1 株の花しか植えられません。

高橋君は、花を植えるポイントを N 個選ぶ必要があります。花壇の見栄えを良くするため、選んだポイントのうち最も左にあるポイントと最も右にあるポイントの間の距離が、できるだけ大きくなるようにしたいと考えています。

さらに、花同士が近すぎると根が競合して成長に悪影響があります。そこで、選んだ N 個のポイントのうち、隣り合うポイント同士（選んだポイントの中で左から i 番目と i+1 番目）の距離の最小値が K メートル以上でなければならないという制約があります。

条件を満たすように N 個のポイントを選んだとき、最も左にあるポイントと最も右にあるポイントの間の距離の最大値を求めてください。条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

2 \leq M \leq 5 \times 10^5
1 \leq N \leq M
1 \leq K \leq 10^{15}
1 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
入力はすべて整数

入力

N M K
D_1 D_2 ... D_{M-1}

1 行目には、植える花の株数を表す N 、ポイントの個数を表す M 、隣り合うポイントの距離の最小値の下限を表す K が、スペース区切りで与えられる。
2 行目には、ポイント i とポイント i+1 の間の距離を表す D_i が M - 1 個、スペース区切りで与えられる。

出力

条件を満たすように N 個のポイントを選んだとき、最も左にあるポイントと最も右にあるポイントの間の距離の最大値を 1 行で出力せよ。条件を満たす選び方が存在しない場合は -1 を出力せよ。

入力例 1

3 5 4
2 3 4 5

出力例 1

入力例 2

2 4 100
10 20 30

出力例 2

-1

入力例 3

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

出力例 3

入力例 4

10 30 15
8 7 10 5 12 6 9 11 4 13 7 8 15 3 14 6 10 9 5 12 8 7 11 4 16 6 9 10 5

出力例 4

入力例 5

1 2 1000000000000000
1

出力例 5

Score : 366 pts

Problem Statement

Takahashi is in charge of managing a flowerbed in a park. He needs to plant N flowers in the flowerbed.

In the flowerbed, there are M planting points arranged in a straight line, numbered Point 1, Point 2, ..., Point M from left to right. The distance between Point i and Point i+1 is D_i meters. At most one flower can be planted at each point.

Takahashi needs to choose N points to plant the flowers. To make the flowerbed look visually appealing, he wants to maximize the distance between the leftmost and rightmost chosen points.

Furthermore, if the flowers are too close to each other, their roots will compete and negatively affect their growth. Therefore, there is a constraint that among the N chosen points, the distance between any two adjacent chosen points (the i-th and (i+1)-th points from the left among the chosen points) must be at least K meters.

Find the maximum possible distance between the leftmost and rightmost points when choosing N points that satisfy the conditions. If there is no choice of points that satisfies the conditions, output -1.

Constraints

2 \leq M \leq 5 \times 10^5
1 \leq N \leq M
1 \leq K \leq 10^{15}
1 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
All input values are integers.

Input

N M K
D_1 D_2 ... D_{M-1}

The first line contains N, the number of flowers to plant, M, the number of points, and K, the minimum required distance between adjacent points, separated by spaces.
The second line contains M - 1 integers D_i, representing the distance between Point i and Point i+1, separated by spaces.

Output

Print the maximum distance between the leftmost and rightmost points among the chosen N points satisfying the conditions in a single line. If no valid choice exists, print -1.

Sample Input 1

3 5 4
2 3 4 5

Sample Output 1

Sample Input 2

2 4 100
10 20 30

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

Sample Input 4

10 30 15
8 7 10 5 12 6 9 11 4 13 7 8 15 3 14 6 10 9 5 12 8 7 11 4 16 6 9 10 5

Sample Output 4

Sample Input 5

1 2 1000000000000000
1

Sample Output 5

D - A Journey of Sugoroku

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はすごろくで遊んでいます。

すごろくの盤面には 1 から N までの番号がついた N 個のマスが一直線上に並んでいます。

各マス i には整数 A_i が書かれています。

高橋君は最初、マス 1 にいます。

彼はこれから K 回の移動を行います。

1 回の移動では、以下の規則に従って現在のマスが更新されます。いずれの場合も移動 1 回分として数えます。

N=1 のとき、高橋君は常にマス 1 に留まります。
N \ge 2 のとき、現在のマスを i として、次のように移動します。
i = N のとき、高橋君はマス N に留まります。
i = 1 のとき、A_1 と A_2 の和が偶数ならばマス 2 に進みます。奇数ならばマス 1 に留まります。
2 \le i \le N-1 のとき、A_i と A_{i+1} の和が偶数ならばマス i+1 に進みます。奇数ならばマス i-1 に戻ります。

K 回の移動をすべて終えたとき、高橋君がいるマスの番号を求めてください。

制約

1 \le N \le 2 \times 10^5
1 \le K \le 10^{18}
-10^9 \le A_i \le 10^9
入力はすべて整数である

入力

N K
A_1 A_2 \cdots A_N

1 行目には、マスの数を表す整数 N と、移動の回数を表す整数 K が、スペース区切りで与えられる。
2 行目には、A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

K 回の移動終了後に高橋君がいるマスの番号を 1 行で出力してください。

入力例 1

4 5
1 3 2 4

出力例 1

入力例 2

3 6
1 2 4

出力例 2

入力例 3

8 17
2 4 6 8 10 11 13 15

出力例 3

入力例 4

15 1000000000000
-10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18

出力例 4

入力例 5

1 1000000000000000000
-123456789

出力例 5

Score : 400 pts

Problem Statement

Takahashi is playing sugoroku (a board game).

The sugoroku board has N squares numbered from 1 to N arranged in a straight line.

Each square i has an integer A_i written on it.

Takahashi starts on square 1.

He will make K moves from now.

In each move, his current square is updated according to the following rules. Each case counts as one move.

When N=1, Takahashi always stays on square 1.
When N \ge 2, let i be his current square. He moves as follows:
If i = N, Takahashi stays on square N.
If i = 1, he advances to square 2 if the sum of A_1 and A_2 is even. He stays on square 1 if it is odd.
If 2 \le i \le N-1, he advances to square i+1 if the sum of A_i and A_{i+1} is even. He goes back to square i-1 if it is odd.

Determine the number of the square Takahashi is on after all K moves are completed.

Constraints

1 \le N \le 2 \times 10^5
1 \le K \le 10^{18}
-10^9 \le A_i \le 10^9
All inputs are integers.

Input

N K
A_1 A_2 \cdots A_N

The first line contains an integer N representing the number of squares and an integer K representing the number of moves, separated by a space.
The second line contains A_1, A_2, \ldots, A_N separated by spaces.

Output

Print the number of the square Takahashi is on after K moves, on a single line.

Sample Input 1

4 5
1 3 2 4

Sample Output 1

Sample Input 2

3 6
1 2 4

Sample Output 2

Sample Input 3

8 17
2 4 6 8 10 11 13 15

Sample Output 3

Sample Input 4

15 1000000000000
-10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18

Sample Output 4

Sample Input 5

1 1000000000000000000
-123456789

Sample Output 5

E - Map Coloring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、ある地域の地図を塗り分ける仕事を任されました。

地図は N 個の区画に分かれており、それぞれの区画にちょうど 1 つの色を塗る必要があります。使える色は K 種類あり、色 1, 色 2, \ldots, 色 K と番号が付けられています。各区画には 1 以上 K 以下の整数（色番号）を 1 つ割り当てます。この色番号は単なるラベルではなく、番号の大小関係が違和感コストの計算に直接用いられます。

区画同士の隣接関係は M 組与えられます。隣接関係を辺とみなすと、区画を頂点としたグラフは木構造をなします（すなわち M = N - 1 であり、グラフは連結です）。i 番目 (1 \leq i \leq M) の隣接関係は区画 u_i と区画 v_i の間にあり、その境界には重み W_i が定められています。区画 u_i に色番号 a を、区画 v_i に色番号 b を割り当てたとき、その境界における違和感コストは W_i \times |a - b| と定義されます。

高橋君は、すべての区画に色を塗ったとき、すべての境界における違和感コストの合計をできるだけ小さくしたいと考えています。ただし、以下の制約があります：

2 種類以上の色を使わなければなりません。すなわち、すべての区画にまったく同じ色番号を割り当てることは許されません。（隣接する区画同士に同じ色番号を割り当てること自体は許されます。）

すべての区画への色の割り当て方のうち、上記の条件を満たしつつ違和感コストの合計が最小となるものを求め、その最小コストを出力してください。

N \geq 2 かつ K \geq 2 であるため、条件を満たす割り当て方は必ず存在することが保証されます。

制約

2 \leq N \leq 2 \times 10^5
M = N - 1（すなわち、隣接関係は木構造をなす）
2 \leq K \leq 10^8
1 \leq u_i < v_i \leq N
1 \leq W_i \leq 10^5
隣接関係に重複はない（同じ区画の組が 2 回以上現れない）
与えられるグラフは連結である
入力はすべて整数である

入力

N M K
u_1 v_1 W_1
u_2 v_2 W_2
\vdots
u_M v_M W_M

1 行目には、区画の数 N、隣接関係の数 M、使える色の種類数 K が、スペース区切りで与えられる。制約より M = N - 1 が保証される。
続く M 行のうち i 行目 (1 \leq i \leq M) には、区画 u_i と区画 v_i が隣接していることと、その境界の重み W_i が、スペース区切りで与えられる。

出力

2 種類以上の色を使うという条件のもとでの、違和感コストの合計の最小値を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

3 2 2
1 2 4
2 3 7

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

2 1 2
1 2 1

出力例 5

Score : 466 pts

Problem Statement

Takahashi has been assigned the task of coloring a map of a certain region.

The map is divided into N districts, and each district must be colored with exactly one color. There are K available colors, numbered 1, 2, \ldots, K. Each district is assigned an integer (color ID) from 1 to K inclusive. These color IDs are not just labels; their numerical differences are directly used to calculate the discomfort cost.

There are M pairs of adjacent districts. If we view the adjacency relations as edges, the graph with districts as vertices forms a tree structure (that is, M = N - 1 and the graph is connected). The i-th (1 \leq i \leq M) adjacency relation is between district u_i and district v_i, and their boundary has a weight W_i. When district u_i is assigned color a and district v_i is assigned color b, the discomfort cost at their boundary is defined as W_i \times |a - b|.

Takahashi wants to minimize the sum of discomfort costs over all boundaries when all districts are colored. However, there is the following constraint:

At least 2 different colors must be used. That is, it is not allowed to assign the exact same color to all districts. (Assigning the same color to adjacent districts is allowed.)

Find the minimum total discomfort cost among all valid color assignments, and output this minimum cost.

Since N \geq 2 and K \geq 2, it is guaranteed that a valid assignment always exists.

Constraints

2 \leq N \leq 2 \times 10^5
M = N - 1 (that is, the adjacency relations form a tree structure)
2 \leq K \leq 10^8
1 \leq u_i < v_i \leq N
1 \leq W_i \leq 10^5
There are no duplicate adjacency relations (the same pair of districts does not appear more than once).
The given graph is connected.
All input values are integers.

Input

N M K
u_1 v_1 W_1
u_2 v_2 W_2
\vdots
u_M v_M W_M

The first line contains the number of districts N, the number of adjacency relations M, and the number of available colors K, separated by spaces. The constraints guarantee M = N - 1.
The i-th of the following M lines (1 \leq i \leq M) contains the adjacent districts u_i and v_i, and the weight of their boundary W_i, separated by spaces.

Output

Print the minimum total discomfort cost under the condition that at least 2 different colors are used, in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

3 2 2
1 2 4
2 3 7

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

2 1 2
1 2 1