AtCoder Daily Training MEDIUM 2025/08/27 20:00start

C - Pentagon

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

以下の図で表される正五角形 P があります。

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しいか判定してください。

制約

S_1,S_2,T_1,T_2 は A, B, C, D, E のいずれかの文字
S_1 \neq S_2
T_1 \neq T_2

入力

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

S_1S_2
T_1T_2

出力

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しい場合 Yes を、等しくない場合 No を出力せよ。

入力例 1

AC
EC

出力例 1

Yes

P の点 A と点 C を結ぶ線分と、P の点 E と点 C を結ぶ線分の長さは等しいです。

入力例 2

DA
EA

出力例 2

No

P の点 D と点 A を結ぶ線分と、P の点 E と点 A を結ぶ線分の長さは等しくありません。

入力例 3

BD
BD

出力例 3

Yes

Score : 200 points

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
S_1 \neq S_2
T_1 \neq T_2

Input

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

S_1S_2
T_1T_2

Output

If the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2, print Yes; otherwise, print No.

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

D - Foreign Exchange

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 150 点

問題文

1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。

高橋君は、下記の操作を好きな回数（ 0 回でも良い）繰り返します。

まず、1 以上 N-1 以下の整数 i を選ぶ。
その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
- 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。

最終的に高橋君が持っている国 N の通貨の単位数としてあり得る最大値を出力してください。

制約

入力される値はすべて整数
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

出力

答えを出力せよ。

入力例 1

出力例 1

以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 A = (A_1, A_2, A_3, A_4) として表します。はじめ、A = (5, 7, 0, 3) です。

下記の通りに 4 回操作を行うことを考えます。

i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (5, 3, 3, 3) となる。
i = 1 を選び、国 1 の通貨 2 単位を支払って、国 2 の通貨 2 単位を獲得する。その結果、A = (3, 5, 3, 3) となる。
i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (3, 1, 6, 3) となる。
i = 3 を選び、国 3 の通貨 5 単位を支払って、国 4 の通貨 2 単位を獲得する。その結果、A = (3, 1, 1, 5) となる。

このとき、最終的に高橋君が持っている国 4 の通貨の単位数は 5 であり、これが考えられる最大値です。

入力例 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

出力例 2

Score: 150 points

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

First, choose an integer i between 1 and N-1, inclusive.
Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
- Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

All input values are integers.
2 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq S_i \leq 10^9

Input

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.

Sample Input 1

Sample Output 1

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

E - Collision 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

xy 座標平面上に N 人の人がいます。人 i は (X_i, Y_i) にいます。すべての人は異なる地点にいます。

L, R からなる長さ N の文字列 S があります。
人 i は S_i = R ならば右向きに、S_i = L ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。

たとえば (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL の場合は次の図のように動きます。

反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか？

制約

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j) である。
X_i, Y_i はすべて整数である。
S は L および R からなる長さ N の文字列である。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

出力

衝突が発生するならば Yes を、発生しないならば No を出力せよ。

入力例 1

出力例 1

Yes

この入力は問題文にある例と同じケースです。
すべての人が歩き続けると人 2 と人 3 が衝突します。よって Yes を出力します。

入力例 2

出力例 2

No

人 1 と人 2 は同じ向きに歩いているので衝突することはありません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All X_i and Y_i are integers.
S is a string of length N consisting of L and R.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

Output

If there will be a collision, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

Sample Output 3

Yes

F - Flavors

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N カップのアイスクリームがあります。
i カップ目の味は F_i 、美味しさは S_i ( S_i は偶数 ) です。

あなたは、 N 個のカップの中から 2 つを選んで食べることにしました。
このときの満足度は次のように定義されます。

食べたアイスクリームの美味しさを s,t ( 但し、 s \ge t ) とする。
- 2 つのカップの味が異なるなら、満足度は \displaystyle s+t である。
- そうでないなら、満足度は \displaystyle s + \frac{t}{2} である。

満足度として達成可能な最大値を求めてください。

制約

入力は全て整数
2 \le N \le 3 \times 10^5
1 \le F_i \le N
2 \le S_i \le 10^9
S_i は偶数

入力

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

N
F_1 S_1
F_2 S_2
\vdots
F_N S_N

出力

答えを整数として出力せよ。

入力例 1

出力例 1

2 カップ目と 4 カップ目のアイスを食べることを考えます。

2 カップ目の味は 2 、美味しさは 10 です。
4 カップ目の味は 3 、美味しさは 6 です。
両者の味は異なるので、満足度は 10+6=16 です。

以上より、満足度 16 を達成できます。
満足度を 16 より大きくすることはできません。

入力例 2

出力例 2

1 カップ目と 4 カップ目のアイスを食べることを考えます。

1 カップ目の味は 4 、美味しさは 10 です。
4 カップ目の味は 4 、美味しさは 12 です。
両者の味は同じなので、満足度は 12+\frac{10}{2}=17 です。

以上より、満足度 17 を達成できます。
満足度を 17 より大きくすることはできません。

Score : 300 points

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

Let s and t (s \ge t) be the deliciousness of the eaten cups.
- If the two cups have different flavors, your satisfaction is \displaystyle s+t.
- Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

All input values are integers.
2 \le N \le 3 \times 10^5
1 \le F_i \le N
2 \le S_i \le 10^9
S_i is even.

Input

Input is given from Standard Input in the following format:

N
F_1 S_1
F_2 S_2
\vdots
F_N S_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Consider eating the second and fourth cups.

The second cup has a flavor of 2 and deliciousness of 10.
The fourth cup has a flavor of 3 and deliciousness of 6.
Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

Sample Output 2

Consider eating the first and fourth cups.

The first cup has a flavor of 4 and deliciousness of 10.
The fourth cup has a flavor of 4 and deliciousness of 12.
Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

G - Max Multiple

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

非負整数列 A=(a_1,a_2,\ldots,a_N) が与えられます。

A の(添え字が相異なる) K 個の項の和として考えられる非負整数の集合を S とします。

S に含まれる D の倍数の最大値を求めてください。ただし、S に D の倍数が含まれない場合、代わりに -1 と出力してください。

制約

1 \leq K \leq N \leq 100
1 \leq D \leq 100
0 \leq a_i \leq 10^9
入力はすべて整数

入力

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

N K D
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

4 2 2
1 2 3 4

出力例 1

A から 2 個の項を選ぶ方法を列挙すると

a_1 と a_2 を選ぶ。選ばれた項の和は 1+2=3 となる。
a_1 と a_3 を選ぶ。選ばれた項の和は 1+3=4 となる。
a_1 と a_4 を選ぶ。選ばれた項の和は 1+4=5 となる。
a_2 と a_3 を選ぶ。選ばれた項の和は 2+3=5 となる。
a_2 と a_4 を選ぶ。選ばれた項の和は 2+4=6 となる。
a_3 と a_4 を選ぶ。選ばれた項の和は 3+4=7 となる。

となり、S=\{3,4,5,6,7\} となります。S に含まれる 2 の倍数のうち最大のものは 6 なので、6 と出力します。

入力例 2

3 1 2
1 3 5

出力例 2

-1

この例では S=\{1,3,5\} です。S に含まれる非負整数はいずれも 2 の倍数でないため、-1 と出力します。

Score : 400 points

Problem Statement

You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).

Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).

Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.

Constraints

1 \leq K \leq N \leq 100
1 \leq D \leq 100
0 \leq a_i \leq 10^9
All values in the input are integers.

Input

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

N K D
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

4 2 2
1 2 3 4

Sample Output 1

Here are all the ways to choose two terms in A.

Choose a_1 and a_2, whose sum is 1+2=3.
Choose a_1 and a_3, whose sum is 1+3=4.
Choose a_1 and a_4, whose sum is 1+4=5.
Choose a_2 and a_3, whose sum is 2+3=5.
Choose a_2 and a_4, whose sum is 2+4=6.
Choose a_3 and a_4, whose sum is 3+4=7.

Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.

Sample Input 2

3 1 2
1 3 5

Sample Output 2

-1

In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.