Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）

A - Tiny Arithmetic Sequence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ 3 の数列 A=(A_1,A_2,A_3) が与えられます。

A を適切に並び替えて等差数列にすることはできますか？

即ち、A_3-A_2=A_2-A_1 を満たすように A を並び替えることはできますか？

制約

1 \leq A_i \leq 100
入力は全て整数

入力

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

A_1 A_2 A_3

出力

A を並び替えて等差数列にできるなら Yes、できないなら No と出力せよ。

入力例 1

5 1 3

出力例 1

Yes

例えば (1,3,5) と並び替えることで等差数列になります。

入力例 2

1 4 3

出力例 2

No

どのように並び替えても A は等差数列になりません。

入力例 3

5 5 5

出力例 3

Yes

A の要素が全て等しい場合や、A が元から等差数列になっている場合もあります。

Score : 100 points

Problem Statement

You are given a sequence of three numbers: A=(A_1,A_2,A_3).

Is it possible to rearrange the elements of A into an arithmetic sequence?

In other words, is it possible to rearrange the elements of A so that A_3-A_2=A_2-A_1?

Constrains

1 \leq A_i \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A_1 A_2 A_3

Output

If it is possible to rearrange the elements of A into an arithmetic sequence, print Yes; otherwise, print No.

Sample Input 1

5 1 3

Sample Output 1

Yes

We can rearrange them into an arithmetic sequence by, for example, making it (1,3,5).

Sample Input 2

1 4 3

Sample Output 2

No

There is no way to rearrange them into an arithmetic sequence.

Sample Input 3

5 5 5

Sample Output 3

Yes

All elements of A may be equal, or A may be an arithmetic sequence already.

B - Do you know the second highest mountain?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

AtCoder国には N 個の山があり、i 個目の山の名前は S_i, 高さは T_i です。

2 番目に高い山の名前を答えてください。N 個の山の名前、高さはそれぞれ相異なることが保証されます。

制約

2 \leq N \leq 1000
1 \leq (S_i の長さ{}) \leq 15
1 \leq T_i \leq 10^5
S_i \neq S_j \ (i \neq j)
T_i \neq T_j \ (i \neq j)
S_i は英小文字、英大文字、数字のみからなる
N,\ T_i は整数

入力

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

N
S_1 T_1
S_2 T_2
\vdots
S_N T_N

出力

2 番目に高い山の名前を出力せよ。

入力例 1

3
Everest 8849
K2 8611
Kangchenjunga 8586

出力例 1

K2

世界で 2 番目に高い山は K2 です。

入力例 2

4
Kita 3193
Aino 3189
Fuji 3776
Okuhotaka 3190

出力例 2

Kita

日本で 2 番目に高い山は北岳です。

入力例 3

4
QCFium 2846
chokudai 2992
kyoprofriends 2432
penguinman 2390

出力例 3

QCFium

Score : 200 points

Problem Statement

The Republic of AtCoder has N mountains. The i-th mountain has a name S_i and a height of T_i.

Return the name of the second highest mountain there. It is guaranteed that all the mountains have different names and different heights.

Constraints

2 \leq N \leq 1000
1 \leq ({}the length of S_i) \leq 15
1 \leq T_i \leq 10^5
S_i \neq S_j \ (i \neq j)
T_i \neq T_j \ (i \neq j)
S_i consists of uppercase English letters, lowercase English letters, and digits.
N and T_i are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 T_1
S_2 T_2
\vdots
S_N T_N

Output

Print the name of the second highest mountain.

Sample Input 1

3
Everest 8849
K2 8611
Kangchenjunga 8586

Sample Output 1

K2

The second highest mountain in the world is K2.

Sample Input 2

4
Kita 3193
Aino 3189
Fuji 3776
Okuhotaka 3190

Sample Output 2

Kita

The second highest mountain in Japan is Kita-dake.

Sample Input 3

4
QCFium 2846
chokudai 2992
kyoprofriends 2432
penguinman 2390

Sample Output 3

QCFium

C - Secret Number

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。

0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 S_0S_1 \ldots S_9 によって表されます。

S_i が o のとき : 数字 i は暗証番号に確実に含まれていた。
S_i が x のとき : 数字 i は暗証番号に確実に含まれていなかった。
S_i が ? のとき : 数字 i が暗証番号に含まれているか分からない。

高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか？

制約

S は o, x, ? のみからなる長さ 10 の文字列

入力

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

出力

答えを出力せよ。

入力例 1

ooo???xxxx

出力例 1

例えば 0123 や 0021 などがあり得ます。

入力例 2

o?oo?oxoxo

出力例 2

あり得る暗証番号が存在しない、即ち答えが 0 通りになる場合もあります。

入力例 3

xxxxx?xxxo

出力例 3

Score : 300 points

Problem Statement

Takahashi has forgotten his PIN. The PIN is a four-digit string consisting of 0, 1, \ldots, 9, and may begin with a 0.

For each digit 0 through 9, Takahashi remembers the following fact, represented by a 10-character string S_0S_1 \ldots S_9:

if S_i is o: he is certain that the PIN contained the digit i;
if S_i is x: he is certain that the PIN did not contain the digit i;
if S_i is ?: he is not sure whether the PIN contained the digit i.

How many strings are there that could be Takahashi's PIN?

Constraints

S is a 10-character string consisting of o, x, and ?.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

ooo???xxxx

Sample Output 1

Some of the possible PINs are 0123 and 0021.

Sample Input 2

o?oo?oxoxo

Sample Output 2

There may be no possible PINs, in which case the answer is 0.

Sample Input 3

xxxxx?xxxo

Sample Output 3

D - Game in Momotetsu World

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

H 行 W 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から i 番目、左から j 番目のマスは、A_{i, j} が + なら青マスであり、- なら赤マスです。
最初、このマス目の一番左上のマスに一つ駒が置かれていて、高橋君と青木君はこの駒を使ってゲームをします。
2 人の得点は最初 0 点ずつです。2 人は、高橋君から始めて交互に次の操作をします。

駒を一つ右または一つ下のマスに動かす。ただし、駒がマス目の外に出るような動かし方はできない。動かした人は、駒の移動後のマスが青マスなら 1 点を得て、赤マスなら 1 点を失う。

どちらかが操作できなくなった時点でゲームは終了します。ゲームの結果は、終了時の 2 人の得点が異なるならば得点の大きい方が勝ち、同じならば引き分けとなります。
両者とも自分の勝敗が最適になるように行動したとき、ゲームの結果を求めてください。

制約

1 \le H, W \le 2000
A_{i, j} は + または -

入力

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

H W
A_{1, 1}A_{1, 2}A_{1, 3} \dots A_{1, W}
A_{2, 1}A_{2, 2}A_{2, 3} \dots A_{2, W}
A_{3, 1}A_{3, 2}A_{3, 3} \dots A_{3, W}
\hspace{2cm}\vdots
A_{H, 1}A_{H, 2}A_{H, 3} \dots A_{H, W}

出力

高橋君が勝つなら Takahashi を、青木君が勝つなら Aoki を、引き分けになるなら Draw を出力せよ。

入力例 1

3 3
---
+-+
+--

出力例 1

Takahashi

高橋君は以下のような戦略で勝つことができます。

まず高橋君が最初に駒を右に動かします。移動先のマスは赤マスなので高橋君は 1 点を失い、高橋君と青木君の得点はそれぞれ -1, 0 となります。

青木君が次に駒を右に動かしたなら、高橋君は駒を下に動かします
青木君が次に駒を下に動かしたなら、高橋君は駒を右に動かします

いずれの場合でも青木君は赤マスに駒を動かして 1 点を失い、高橋君は青マスに駒を動かして 1 点を得るため、両者の得点はそれぞれ 0, -1 となります。
現在駒はマス目の上から 2 番目、左から 3 番目のマスにあるので、次の移動では青木君は下に動かすほかなく、移動先が赤マスなので両者の得点はそれぞれ 0, -2 となります。
もう駒は右にも下にも動かせないのでゲームは終了し、得点の大きい高橋君が勝利します。

入力例 2

2 4
+++-
-+-+

出力例 2

Aoki

青木君は、高橋君がどのように操作しても、上手く操作すれば勝つことができます。

入力例 3

1 1
-

出力例 3

Draw

この場合ゲームは直ちに終了し、両者得点 0 であるため結果は引き分けとなります。

Score : 400 points

Problem Statement

We have a grid with H rows and W columns of squares, where each square is blue or red. The square at the i-th row and j-th column is blue if A_{i, j} is +, and red if A_{i, j} is -.
There is a piece on this grid, which is initially placed on the top-left square. Takahashi and Aoki will play a game using this piece.
Each of the two players has 0 points in the beginning. They will alternately do the following operation, with Takahashi going first:

Move the piece one square right or one square down. It is not allowed to move the piece outside the grid. Then, the player (who moved the piece) gets one point if the piece is now on a blue square, and loses one point if the piece is now on a red square.

The game ends when one of the players is unable to do the operation. Then, the player with the greater number of points wins the game if they have different numbers of points. Otherwise, the game is drawn.
Find the result of the game when both players play the game to get the best outcome.

Constraints

1 \le H, W \le 2000
A_{i, j} is + or -.

Input

Input is given from Standard Input in the following format:

H W
A_{1, 1}A_{1, 2}A_{1, 3} \dots A_{1, W}
A_{2, 1}A_{2, 2}A_{2, 3} \dots A_{2, W}
A_{3, 1}A_{3, 2}A_{3, 3} \dots A_{3, W}
\hspace{2cm}\vdots
A_{H, 1}A_{H, 2}A_{H, 3} \dots A_{H, W}

Output

If Takahashi will win, print Takahashi; if Aoki will win, print Aoki; if the game will be drawn, print Draw.

Sample Input 1

3 3
---
+-+
+--

Sample Output 1

Takahashi

Takahashi has a winning strategy described below.

First, Takahashi moves the piece right, which makes him lose one point because the piece goes to a red square. Now, Takahashi has -1 point and Aoki has 0 points. Then,

if Aoki moves the piece right, Takahashi moves it down;
if Aoki moves the piece down, Takahashi moves it right.

In either case, Aoki moves the piece to a red square losing one point, and Takahashi moves the piece to a blue square getting one point, which means now Takahashi has 0 points and Aoki has -1 point.
The piece is now on the square at the 2-nd row from the top and 3-rd column from the left, and Aoki can only choose to move it down, to a red square. Now, Takahashi has 0 points and Aoki has -2 points.
The piece cannot move right or down anymore, so the game ends. Since Takahashi has the greater number of points, he wins.

Sample Input 2

2 4
+++-
-+-+

Sample Output 2

Aoki

Aoki can win the game, regardless of what choices Takahashi makes.

Sample Input 3

1 1
-

Sample Output 3

Draw

In this case, the game immediately ends. Since both players have 0 points, the game is drawn.

E - Xor Distances

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点の重み付き木があります。i 本目の辺は頂点 u_i と頂点 v_i を双方向に結んでいて、その重みは w_i です。

頂点の組 (x,y) について、\text{dist}(x,y) を以下のように定めます。

x から y への最短パスに含まれる辺全ての重みの XOR

1 \leq i \lt j \leq N を満たす全ての組 (i,j) について \text{dist}(i,j) を求め、その総和を (10^9+7) で割った余りを出力してください。

\text{ XOR } とは

整数 a, b のビットごとの排他的論理和 a \text{ XOR } b は、以下のように定義されます。

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

例えば、3 \text{ XOR } 5 = 6 となります (二進表記すると: 011 \text{ XOR } 101 = 110)。

制約

2 \leq N \leq 2 \times 10^5
1 \leq u_i \lt v_i \leq N
0 \leq w_i \lt 2^{60}
与えられるグラフは木
入力は全て整数

入力

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

N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}

出力

\text{dist}(i,j) の総和を (10^9+7) で割った余りを出力せよ。

入力例 1

3
1 2 1
1 3 3

出力例 1

\text{dist}(1,2)=1, \text{dist}(1,3)=3, \text{dist}(2,3)=2 であり、これらの総和は 6 です。

入力例 2

出力例 2

入力例 3

10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

出力例 3

241240228

(10^9+7) で割った余りを出力してください。

Score : 500 points

Problem Statement

We have a weighted tree with N vertices. The i-th edge connects Vertex u_i and Vertex v_i bidirectionally and has a weight w_i.

For a pair of vertices (x,y), let us define \text{dist}(x,y) as follows:

the XOR of the weights of the edges in the shortest path from x to y.

Find \text{dist}(i,j) for every pair (i,j) such that 1 \leq i \lt j \leq N, and print the sum of those values modulo (10^9+7).

What is \text{ XOR }?

The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:

When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.

For example, we have 3\ \mathrm{XOR}\ 5 = 6 (in base two: 011\ \mathrm{XOR}\ 101 = 110).

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq u_i \lt v_i \leq N
0 \leq w_i \lt 2^{60}
The given graph is a tree.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}

Output

Print the sum of \text{dist}(i,j), modulo (10^9+7).

Sample Input 1

3
1 2 1
1 3 3

Sample Output 1

We have \text{dist}(1,2)=1, \text{dist}(1,3)=3, and \text{dist}(2,3)=2, for the sum of 6.

Sample Input 2

Sample Output 2

Sample Input 3

10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

Sample Output 3

241240228

Print the sum modulo (10^9+7).

F - Insertion Sort

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号が振られた N 人の人が左右一列に並んでいます。はじめ、左から i 番目の人の番号は P_i です。

あなたの目標は、以下の 3 種類の操作を繰り返すことで人々が左から番号の昇順で並んでいるようにすることです。これらの操作は、任意の順に何回でも（0 回でもよい）行うことができます。

整数 i\ (1 \leq i \leq N) を選ぶ。コスト A_i を払い、人 i を好きな位置に移動させる。
整数 i\ (1 \leq i \leq N) を選ぶ。コスト B_i を払い、人 i を左端に移動させる。
整数 i\ (1 \leq i \leq N) を選ぶ。コスト C_i を払い、人 i を右端に移動させる。

目標を達成するまでに支払う合計コストを最小化してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq P_i \leq N
1 \leq A_i,B_i,C_i \leq 10^9
P_i \neq P_j\ (i \neq j)
入力は全て整数

入力

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

N
P_1 P_2 \ldots P_N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

出力

目標を達成するまでに支払う合計コストの最小値を出力せよ。

入力例 1

出力例 1

コスト C_3=6 を払って人 3 を右端に動かすことで、人々を昇順に並び替えることができます。

これより合計コストが低い並び替え方は存在しないので、答えは 6 となります。

入力例 2

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

出力例 2

以下の順に操作を行うことで最小値を達成可能です。

コスト B_1=8 を払い、人 1 を左端に移動させる。
コスト C_5=5 を払い、人 5 を右端に移動させる。
コスト C_6=2 を払い、人 6 を右端に移動させる。

入力例 3

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

出力例 3

入力例 4

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705

出力例 4

Score : 600 points

Problem Statement

There are N people, who are given ID numbers 1 through N, standing in a row from left to right. Initially, the ID number of the i-th person from the left is P_i.

Your objective is to rearrange the people in ascending order of the ID number from left to right, by repeatedly doing the three kinds of operations below. You can do these operations any number of times (possibly zero) in any order.

Choose an integer i\ (1 \leq i \leq N), pay the cost A_i, and move Person i (the person with the ID number i) to any position of your choice.
Choose an integer i\ (1 \leq i \leq N), pay the cost B_i, and move Person i to the left end of the row.
Choose an integer i\ (1 \leq i \leq N), pay the cost C_i, and move Person i to the right end of the row.

Minimize the total cost you pay before achieving the objective.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq P_i \leq N
1 \leq A_i,B_i,C_i \leq 10^9
P_i \neq P_j\ (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

Output

Print the minimum total cost you need to pay before achieving the objective.

Sample Input 1

Sample Output 1

You can rearrange the people in ascending order of the ID number by paying the cost C_3=6 to move Person 3 to the right end.

There is no way to rearrange the people that costs less, so the answer is 6.

Sample Input 2

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

Sample Output 2

The following sequence of operations minimizes the total cost:

pay the cost B_1=8 to move Person 1 to the left end;
pay the cost C_5=5 to move Person 5 to the right end;
pay the cost C_6=2 to move Person 6 to the right end.

Sample Input 3

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

Sample Output 3

Sample Input 4

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705