AtCoder Daily Training MEDIUM 2024/1/11 18:30start

C - AtCoder Quiz

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。

AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?

制約

S_1 , S_2 , S_3 はそれぞれ、 ABC , ARC , AGC , AHC のいずれかである。
S_1 , S_2 , S_3 は相異なる。

入力

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

S_1
S_2
S_3

出力

答えを出力せよ。

入力例 1

ARC
AGC
AHC

出力例 1

ABC

ARC , AGC , AHC の 3つが入力として与えられているので、残りの 1 つはABC です。

入力例 2

AGC
ABC
ARC

出力例 2

AHC

Score : 200 points

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
S_1, S_2, and S_3 are pairwise different.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

Print the answer.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

D - Cutoff

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下の手順で行われる試験があります。

試験は 1 ラウンド目から N ラウンド目までの N ラウンドからなる。
各ラウンドに対し、 0 以上 100 以下の整数でスコアが与えられる。
N ラウンドのスコアのうち、最高スコアと最低スコアを除いた N-2 ラウンドのスコアの合計が最終結果となる。
- 厳密には、各ラウンドのスコアを昇順に並べた列を S=(S_1,S_2,\dots,S_N) としたとき、最終結果は S_2+S_3+\dots+S_{N-1} となる。

現在、試験のうち N-1 ラウンドが終了し、 i ラウンド目のスコアは A_i でした。
最終結果を X 以上とするために N ラウンド目に取るべきスコアの最小値を出力してください。
但し、 N ラウンド目にどのようなスコアを取っても最終結果が X 以上にならない場合、代わりに -1 と出力してください。
なお、 N ラウンド目に取りうるスコアは 0 以上 100 以下の整数であることに注意してください。

制約

入力は全て整数
3 \le N \le 100
0 \le X \le 100 \times (N-2)
0 \le A_i \le 100

入力

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

N X
A_1 A_2 \dots A_{N-1}

出力

答えを出力せよ。

入力例 1

5 180
40 60 80 50

出力例 1

4 ラウンド目までのスコアは 40,60,80,50 でした。
5 ラウンド目にスコア 70 を取ると、スコアを昇順に並べた列は S=(40,50,60,70,80) となり、最終結果は 50+60+70=180 となります。
なお、最終結果を 180 以上にするために取るべきスコアの最小値が 70 であることが示せます。

入力例 2

3 100
100 100

出力例 2

2 ラウンド目までのスコアは 100,100 でした。
3 ラウンド目にスコア 0 を取ると、スコアを昇順に並べた列は S=(0,100,100) となり、最終結果は 100 となります。
最大スコアである 100 が複数ありますが、そのうち 1 つしか除かれないことに注意してください。(最小スコアについても同様です)
なお、最終結果を 100 以上にするために取るべきスコアの最小値が 0 であることが示せます。

入力例 3

5 200
0 0 99 99

出力例 3

-1

4 ラウンド目までのスコアは 0,0,99,99 でした。
5 ラウンド目にどのようなスコアを取っても、最終結果を 200 以上にすることができないことが示せます。

入力例 4

10 480
59 98 88 54 70 24 8 94 46

出力例 4

Score : 200 points

Problem Statement

There is an exam structured as follows.

The exam consists of N rounds called round 1 to N.
In each round, you are given an integer score between 0 and 100, inclusive.
Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
- Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.

Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.

Constraints

All input values are integers.
3 \le N \le 100
0 \le X \le 100 \times (N-2)
0 \le A_i \le 100

Input

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

N X
A_1 A_2 \dots A_{N-1}

Output

Print the answer.

Sample Input 1

5 180
40 60 80 50

Sample Output 1

Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.

Sample Input 2

3 100
100 100

Sample Output 2

Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.

Sample Input 3

5 200
0 0 99 99

Sample Output 3

-1

Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.

Sample Input 4

10 480
59 98 88 54 70 24 8 94 46

Sample Output 4

E - Route Map

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 鉄道のとある路線には N 個の駅が存在し、始点から終点に向かって i \, (1 \leq i \leq N) 番目の駅の名前は S_i です。

普通列車は全ての駅に止まりますが、急行列車は全ての駅に止まるとは限りません。具体的には、急行列車は M \, (M \leq N) 個の駅にのみ止まり、j \, (1 \leq j \leq M) 番目に止まる駅の名前は T_j です。
ただし、T_1 = S_1 かつ T_M = S_N、すなわち急行列車は始点と終点の両方に止まることが保証されます。

N 個の駅それぞれについて、その駅に急行列車が止まるかどうか判定してください。

制約

2 \leq M \leq N \leq 10^5
N, M は整数
S_i \, (1 \leq i \leq N) は英小文字のみからなる 1 文字以上 10 文字以下の文字列
S_i \neq S_j \, (i \neq j)
T_1 = S_1 かつ T_M = S_N
(T_1, \dots, T_M) は (S_1, \dots, S_N) から 0 個以上の文字列を選んで取り除き、残った文字列を元の順序で並べることで得られる

入力

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

N M
S_1 \ldots S_N
T_1 \ldots T_M

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、始点から終点に向かって i 番目の駅に急行列車が止まるなら Yes、そうでないなら No と出力せよ。

入力例 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

出力例 1

Yes
No
Yes
No
Yes

入力例 2

7 7
a t c o d e r
a t c o d e r

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

急行列車が全ての駅に止まることもあります。

Score : 300 points

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

2 \leq M \leq N \leq 10^5
N and M are integers.
S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
S_i \neq S_j \, (i \neq j)
T_1 = S_1 and T_M = S_N.
(T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Input

Input is given from Standard Input in the following format:

N M
S_1 \ldots S_N
T_1 \ldots T_M

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain Yes if express trains stop at the i-th station from the starting station, and No otherwise.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

F - Centers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

1\leq N \leq 10^5
1 \leq A_j \leq N
i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2

A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

入力例 3

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

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

1\leq N \leq 10^5
1 \leq A_j \leq N
i occurs in A exactly three times, for each i=1,2,\dots,N.
All input values are integers.

Input

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

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

Sample Input 3

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

Sample Output 3

3 4 1 2

G - Shift vs. CapsLock

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

あなたのパソコンのキーボードには、a キー・Shift キー・CapsLock キーの 3 種類のキーがあります。また、CapsLock キーにはランプが付いています。初め、CapsLock キーのランプは OFF であり、パソコンの画面には空文字列が表示されています。

あなたは、以下の 3 種類の操作のうち 1 つを選んで実行するということを 0 回以上何度でも行うことができます。

X ミリ秒かけて a キーのみを押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に a が付け足され、ON ならば A が付け足される。
Y ミリ秒かけて Shift キーと a キーを同時に押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に A が付け足され、 ON ならば a が付け足される。
Z ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが OFF ならば ON に、ON ならば OFF に切り替わる。

A と a からなる文字列 S が与えられます。画面の文字列を S に一致させるのに必要な最短の時間は何ミリ秒かを求めてください。

制約

1 \leq X,Y,Z \leq 10^9
X,Y,Z は整数
1 \leq |S| \leq 3 \times 10^5
S は A と a からなる文字列

入力

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

X Y Z
S

出力

答えを出力せよ。

入力例 1

1 3 3
AAaA

出力例 1

以下のように操作を行うと 9 ミリ秒で画面の文字列を AAaA に一致させられます。これが最短の時間です。

Z(=3) ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが ON になる。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。
Y(=3) ミリ秒かけて Shift キーと a キーを同時に押す。a が画面の文字列の末尾に付け足される。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。

入力例 2

1 1 100
aAaAaA

出力例 2

入力例 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

出力例 3

Score : 400 points

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

1 \leq X,Y,Z \leq 10^9
X, Y, and Z are integers.
1 \leq |S| \leq 3 \times 10^5
S is a string consisting of A and a.

Input

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

X Y Z
S

Output

Print the answer.

Sample Input 1

1 3 3
AAaA

Sample Output 1

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA