AtCoder Regular Contest 063

C - 1D Reversi

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

きつねの次郎と三郎が一次元リバーシで遊んでいます。一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、列の右端か左端に新たに石を打っていきます。通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、挟まれた黒の石は白い石に変わります。

ゲームの途中で三郎に急用ができて帰ってしまうことになりました。このとき、盤面の状態は文字列 S で表されます。石は |S| (文字列の長さ) 個並んでおり、左から i (1 ≦ i ≦ |S|) 個目の石の色は、S の i 文字目が B のとき黒、W のとき白です。

次郎は現在の盤面に対して、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。最小で何個の石を打てばよいかを求めてください。

制約

1 ≦ |S| ≦ 10^5
S に含まれる文字は B または W のいずれかである

入力

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

出力

全ての石を同じ色にするために打つ必要のある石の個数の最小値を出力せよ。

入力例 1

BBBWW

出力例 1

たとえば右端に黒い石を打つとすべての白い石を黒い石にすることができます。他にも、左端に白い石を打つことでもすべての石の色を同じにできます。

いずれの場合も 1 個の石ですべての石を同じ色にすることができるので、1 を出力します。

入力例 2

WWWWWW

出力例 2

最初から全ての石が同じ色の場合、新たに石を打つ必要はありません。

入力例 3

WBWBWBWBWB

出力例 3

Score : 300 points

Problem Statement

Two foxes Jiro and Saburo are playing a game called 1D Reversi. This game is played on a board, using black and white stones. On the board, stones are placed in a row, and each player places a new stone to either end of the row. Similarly to the original game of Reversi, when a white stone is placed, all black stones between the new white stone and another white stone, turn into white stones, and vice versa.

In the middle of a game, something came up and Saburo has to leave the game. The state of the board at this point is described by a string S. There are |S| (the length of S) stones on the board, and each character in S represents the color of the i-th (1 ≦ i ≦ |S|) stone from the left. If the i-th character in S is B, it means that the color of the corresponding stone on the board is black. Similarly, if the i-th character in S is W, it means that the color of the corresponding stone is white.

Jiro wants all stones on the board to be of the same color. For this purpose, he will place new stones on the board according to the rules. Find the minimum number of new stones that he needs to place.

Constraints

1 ≦ |S| ≦ 10^5
Each character in S is B or W.

Input

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

Output

Print the minimum number of new stones that Jiro needs to place for his purpose.

Sample Input 1

BBBWW

Sample Output 1

By placing a new black stone to the right end of the row of stones, all white stones will become black. Also, by placing a new white stone to the left end of the row of stones, all black stones will become white.

In either way, Jiro's purpose can be achieved by placing one stone.

Sample Input 2

WWWWWW

Sample Output 2

If all stones are already of the same color, no new stone is necessary.

Sample Input 3

WBWBWBWBWB

Sample Output 3

D - An Invisible Hand

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

N 個の町が一直線上に並んでいます。行商人の高橋君は町 1 から出発し、リンゴの売買をしながら町 N へと向かいます。

はじめ高橋君は町 1 におり、リンゴを 1 つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。

移動: 町 i (i < N) にいるとき、町 i + 1 へ移動する。
リンゴの売買: リンゴを好きな個数だけ売買する。ここで、町 i (1 ≦ i ≦ N) ではリンゴの買値も売値もともに A_i 円とする。ここで A_i は相異なる整数です。

1 つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) T 個以下にしなくてはなりません。

高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。

この旅に先立って、青木君は任意の町 i に対して A_i を好きな非負整数 A_i' に変えるという操作を好きなだけ行うことができます。ただし、この操作は行うごとに |A_i - A_i'| のコストがかかります。操作後には異なる町の間でリンゴの値段が同じになっていても構いません。

青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 1 円下げることです。合計コストの最小値を求めてください。

ただし、元の状態で高橋君が 1 円以上の利益を上げられることは仮定して構いません。

制約

1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)
A_i は相異なる
2 ≦ T ≦ 10^9
入力の状態では高橋君は 1 円以上の利益を上げられることが保証される

入力

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

N T
A_1 A_2 ... A_N

出力

高橋君の収益を少なくとも 1 円下げるために必要な合計コストの最小値を出力せよ。

入力例 1

3 2
100 50 200

出力例 1

この入力の状態では、高橋君は次のようにして最大の利益である 150 円を達成することができます。

町 1 から町 2 へ移動する。
町 2 で 50 円を支払い、リンゴを 1 個買う。
町 2 から町 3 へ移動する。
町 3 で 200 円でリンゴを 1 個売る。

たとえば、青木君が町 2 のリンゴの値段を 50 円から 51 円に変えると、高橋君はどのようにしても 150 円の利益を上げることができなくなります。すなわち、コスト 1 で高橋君の利益を少なくとも 1 円下げることが可能であり、答えは 1 となります。

他にも、町 3 のリンゴの値段を 200 円から 199 円に変えることでもコスト 1 で高橋君の利益を下げることが可能です。

入力例 2

5 8
50 30 40 10 20

出力例 2

入力例 3

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

出力例 3

Score : 400 points

Problem Statement

There are N towns located in a line, conveniently numbered 1 through N. Takahashi the merchant is going on a travel from town 1 to town N, buying and selling apples.

Takahashi will begin the travel at town 1, with no apple in his possession. The actions that can be performed during the travel are as follows:

Move: When at town i (i < N), move to town i + 1.
Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for A_i yen (the currency of Japan) at town i (1 ≦ i ≦ N), where A_i are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most T. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change A_i into another arbitrary non-negative integer A_i' for any town i, any number of times. The cost of performing this operation is |A_i - A_i'|. After performing this operation, different towns may have equal values of A_i.

Aoki's objective is to decrease Takahashi's expected profit by at least 1 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 1 yen.

Constraints

1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)
A_i are distinct.
2 ≦ T ≦ 10^9
In the initial state, Takahashi's expected profit is at least 1 yen.

Input

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

N T
A_1 A_2 ... A_N

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least 1 yen.

Sample Input 1

3 2
100 50 200

Sample Output 1

In the initial state, Takahashi can achieve the maximum profit of 150 yen as follows:

Move from town 1 to town 2.
Buy one apple for 50 yen at town 2.
Move from town 2 to town 3.
Sell one apple for 200 yen at town 3.

If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1, thus the answer is 1.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 3 from 200 yen to 199 yen.

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

Sample Input 3

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

Sample Output 3

E - Integers on a Tree

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

N 頂点の木があり、頂点には 1, 2, ..., N と番号が振られています。i (1 ≦ i ≦ N - 1) 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

高橋君は木の K 個の頂点に整数を書き込みました。具体的には、各 1 ≦ j ≦ K について、頂点 V_j に整数 P_j を書き込みました。その後、高橋君は居眠りを始めました。

木を見つけた青木君は、残りのすべての頂点に整数を書き込み、高橋君を驚かせようとしています。高橋君を驚かせるためには、木が次の条件を満たさなければなりません。

条件: 辺で直接結ばれた 2 つの頂点に書かれている整数の差がちょうど 1 である。

残りのすべての頂点に書き込む整数を工夫することで、木が条件を満たすようにできるか判定してください。もし可能な場合は、どのように整数を書き込めばよいかを具体的にひとつ求めて下さい。

制約

1 ≦ N ≦ 10^5
1 ≦ K ≦ N
1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
1 ≦ V_j ≦ N (1 ≦ j ≦ K) (21:18, 制約の誤記を修正)
0 ≦ P_j ≦ 10^6 (1 ≦ j ≦ K)
与えられるグラフは木になることが保証される
V_j はすべて相異なる

入力

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

N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K

出力

残りのすべての頂点に書き込む整数を工夫することで木が条件を満たすようにできるならば Yes を、できないならば No を出力せよ。

条件を満たせる場合、追加で N 行出力せよ。このうちの v (1 ≦ v ≦ N) 行目には、頂点 v に書かれる整数を出力せよ。条件を満たすような整数の書き込み方が複数ある場合、そのうちいずれかひとつを出力すればよい。

入力例 1

出力例 1

Yes
5
6
6
5
7

はじめ、木は以下の図のような状態である。頂点のそばに書かれた数が頂点番号を、頂点の中に書かれた青い数が元から書き込まれていた整数を表す。

青木君はたとえば次のように残りの頂点に整数を書き込むことで木が条件を満たすようにできる。これは出力例 1 に対応している。

木が条件を満たしていれば、これとは異なった出力でも AC となることに注意せよ。たとえば、入力例 1 に対しては

Yes
7
6
8
7
7

という出力でも正答となる。

入力例 2

出力例 2

No

入力例 3

出力例 3

Yes
0
-1
-2
-3

新たに書き込む整数は負になったり 10^6 を超えたりしても構わない。

Score : 800 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1, 2, ..., N. The i-th (1 ≦ i ≦ N - 1) edge connects the two vertices A_i and B_i.

Takahashi wrote integers into K of the vertices. Specifically, for each 1 ≦ j ≦ K, he wrote the integer P_j into vertex V_j. The remaining vertices are left empty. After that, he got tired and fell asleep.

Then, Aoki appeared. He is trying to surprise Takahashi by writing integers into all empty vertices so that the following condition is satisfied:

Condition: For any two vertices directly connected by an edge, the integers written into these vertices differ by exactly 1.

Determine if it is possible to write integers into all empty vertices so that the condition is satisfied. If the answer is positive, find one specific way to satisfy the condition.

Constraints

1 ≦ N ≦ 10^5
1 ≦ K ≦ N
1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
1 ≦ V_j ≦ N (1 ≦ j ≦ K) (21:18, a mistake in this constraint was corrected)
0 ≦ P_j ≦ 10^5 (1 ≦ j ≦ K)
The given graph is a tree.
All v_j are distinct.

Input

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

N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K

Output

If it is possible to write integers into all empty vertices so that the condition is satisfied, print Yes. Otherwise, print No.

If it is possible to satisfy the condition, print N lines in addition. The v-th (1 ≦ v ≦ N) of these N lines should contain the integer that should be written into vertex v. If there are multiple ways to satisfy the condition, any of those is accepted.

Sample Input 1

Sample Output 1

Yes
5
6
6
5
7

The figure below shows the tree when Takahashi fell asleep. For each vertex, the integer written beside it represents the index of the vertex, and the integer written into the vertex is the integer written by Takahashi.

Aoki can, for example, satisfy the condition by writing integers into the remaining vertices as follows:

This corresponds to Sample Output 1. Note that other outputs that satisfy the condition will also be accepted, such as:

Yes
7
6
8
7
7

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

Yes
0
-1
-2
-3

The integers written by Aoki may be negative or exceed 10^6.

F - Snuke's Coloring 2

Time Limit: 4 sec / Memory Limit: 256 MB

配点 : 1600 点

問題文

xy 平面上に、左下の頂点の座標が (0, 0)、右上の頂点の座標が (W, H) で、各辺が x 軸か y 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。

すぬけ君はこの長方形の中に N 個の点を打ちました。i 個目 (1 ≦ i ≦ N) の点の座標は (x_i, y_i) でした。

すぬけ君は各 1 ≦ i ≦ N に対し、長方形の

x < x_i をみたす領域
x > x_i をみたす領域
y < y_i をみたす領域
y > y_i をみたす領域

の 4 つの中から 1 つを選び、その領域を黒く塗ります。

塗りつぶしが終わったあとに残る白い長方形の周長を最大化するように塗る領域を選ぶとき、その最大の周長を求めてください。

制約

1 ≦ W, H ≦ 10^8
1 ≦ N ≦ 3 \times 10^5
0 ≦ x_i ≦ W (1 ≦ i ≦ N)
0 ≦ y_i ≦ H (1 ≦ i ≦ N)
W, H (21:32 追記), x_i, y_i は整数である
i ≠ j ならば x_i ≠ x_j かつ y_i ≠ y_j である

入力

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

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

出力

塗りつぶしが終わったあとに残る白い長方形の周長の最大値を出力せよ。

入力例 1

出力例 1

このケースでは、すぬけ君は以下の図のように長方形を塗りつぶすと残った白い長方形の周長が 32 となり、これが最大値である。

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

100000000 100000000 1
3 4

出力例 4

399999994

Score : 1600 points

Problem Statement

There is a rectangle in the xy-plane, with its lower left corner at (0, 0) and its upper right corner at (W, H). Each of its sides is parallel to the x-axis or y-axis. Initially, the whole region within the rectangle is painted white.

Snuke plotted N points into the rectangle. The coordinate of the i-th (1 ≦ i ≦ N) point was (x_i, y_i).

Then, for each 1 ≦ i ≦ N, he will paint one of the following four regions black:

the region satisfying x < x_i within the rectangle
the region satisfying x > x_i within the rectangle
the region satisfying y < y_i within the rectangle
the region satisfying y > y_i within the rectangle

Find the longest possible perimeter of the white region of a rectangular shape within the rectangle after he finishes painting.

Constraints

1 ≦ W, H ≦ 10^8
1 ≦ N ≦ 3 \times 10^5
0 ≦ x_i ≦ W (1 ≦ i ≦ N)
0 ≦ y_i ≦ H (1 ≦ i ≦ N)
W, H (21:32, added), x_i and y_i are integers.
If i ≠ j, then x_i ≠ x_j and y_i ≠ y_j.

Input

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

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the longest possible perimeter of the white region of a rectangular shape within the rectangle after Snuke finishes painting.

Sample Input 1

Sample Output 1

In this case, the maximum perimeter of 32 can be obtained by painting the rectangle as follows:

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

100000000 100000000 1
3 4

Sample Output 4

399999994