AtCoder Beginner Contest 141

A - Weather Prediction

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

高橋君の住む町の天気は、一日ごとに晴れ(Sunny)、くもり(Cloudy)、雨(Rainy)、晴れ、くもり、雨、… と周期的に変化します。

今日の天気を表す文字列 S が与えられるので、明日の天気を予測してください。

制約

S は Sunny, Cloudy, Rainy のいずれかである

入力

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

出力

明日の天気を入力と同じ形式で出力せよ。

入力例 1

Sunny

出力例 1

Cloudy

高橋くんの住む町では、晴れの日の次の日の天気はくもりです。

入力例 2

Rainy

出力例 2

Sunny

Score: 100 points

Problem Statement

The weather in Takahashi's town changes day by day, in the following cycle: Sunny, Cloudy, Rainy, Sunny, Cloudy, Rainy, ...

Given is a string S representing the weather in the town today. Predict the weather tomorrow.

Constraints

S is Sunny, Cloudy, or Rainy.

Input

Input is given from Standard Input in the following format:

Output

Print a string representing the expected weather tomorrow, in the same format in which input is given.

Sample Input 1

Sunny

Sample Output 1

Cloudy

In Takahashi's town, a sunny day is followed by a cloudy day.

Sample Input 2

Rainy

Sample Output 2

Sunny

B - Tap Dance

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

高橋君はタップダンスをすることにしました。タップダンスの動きは文字列 S で表され、S の各文字は L, R, U, D のいずれかです。各文字は足を置く位置を表しており、1 文字目から順番に踏んでいきます。

S が以下の 2 条件を満たすとき、またその時に限り、S を「踏みやすい」文字列といいます。

奇数文字目がすべて R, U, D のいずれか。
偶数文字目がすべて L, U, D のいずれか。

S が「踏みやすい」文字列なら Yes を、そうでなければ No を出力してください。

制約

S は長さ 1 以上 100 以下の文字列
S の各文字は L, R, U, D のいずれか

入力

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

出力

S が「踏みやすい」文字列なら Yes を、そうでなければ No を出力してください。

入力例 1

RUDLUDR

出力例 1

Yes

1, 3, 5, 7 文字目は R, U, D のいずれかです。

2, 4, 6 文字目は L, U, D のいずれかです。

したがって、この S は「踏みやすい」文字列です。

入力例 2

DULL

出力例 2

No

3 文字目が R, U, D のいずれでもないので、この S は「踏みやすい」文字列ではありません。

入力例 3

UUUUUUUUUUUUUUU

出力例 3

Yes

入力例 4

ULURU

出力例 4

No

入力例 5

RDULULDURURLRDULRLR

出力例 5

Yes

Score: 200 points

Problem Statement

Takahashi will do a tap dance. The dance is described by a string S where each character is L, R, U, or D. These characters indicate the positions on which Takahashi should step. He will follow these instructions one by one in order, starting with the first character.

S is said to be easily playable if and only if it satisfies both of the following conditions:

Every character in an odd position (1-st, 3-rd, 5-th, \ldots) is R, U, or D.
Every character in an even position (2-nd, 4-th, 6-th, \ldots) is L, U, or D.

Your task is to print Yes if S is easily playable, and No otherwise.

Constraints

S is a string of length between 1 and 100 (inclusive).
Each character of S is L, R, U, or D.

Input

Input is given from Standard Input in the following format:

Output

Print Yes if S is easily playable, and No otherwise.

Sample Input 1

RUDLUDR

Sample Output 1

Yes

Every character in an odd position (1-st, 3-rd, 5-th, 7-th) is R, U, or D.

Every character in an even position (2-nd, 4-th, 6-th) is L, U, or D.

Thus, S is easily playable.

Sample Input 2

DULL

Sample Output 2

No

The 3-rd character is not R, U, nor D, so S is not easily playable.

Sample Input 3

UUUUUUUUUUUUUUU

Sample Output 3

Yes

Sample Input 4

ULURU

Sample Output 4

No

Sample Input 5

RDULULDURURLRDULRLR

Sample Output 5

Yes

C - Attack Survival

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

問題文

高橋君は早押しクイズの大会を開くことにしました。スコアボードの作成を任されたキザハシ君は、次のルールを持つラウンドのポイントを管理するプログラムを書くのに苦戦しています。

このラウンドの参加者は N 人であり、1 から N までの番号がついています。ラウンド開始時点では全員が K ポイントを持っています。

誰かが問題に正解すると、その人以外の N-1 人のポイントが 1 減ります。これ以外によるポイントの変動はありません。

ラウンド終了時にポイントが 0 以下の参加者は敗退し、残りの参加者が勝ち抜けます。

このラウンドでは Q 回の正解が出て、i 番目に正解したのは参加者 A_i でした。キザハシ君の代わりに、N 人の参加者のそれぞれが勝ち抜けたか敗退したかを求めるプログラムを作成してください。

制約

入力はすべて整数
2 \leq N \leq 10^5
1 \leq K \leq 10^9
1 \leq Q \leq 10^5
1 \leq A_i \leq N\ (1 \leq i \leq Q)

入力

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

N K Q
A_1
A_2
.
.
.
A_Q

出力

N 行出力してください。i 行目には、参加者 i が勝ち抜けたなら Yes を、敗退したなら No を出力してください。

入力例 1

出力例 1

No
No
Yes
No
No
No

はじめ、各参加者の持つポイントは (3, 3, 3, 3, 3, 3) です。

参加者 3 が正解し、各参加者のポイントは (2, 2, 3, 2, 2, 2) になります。
参加者 1 が正解し、各参加者のポイントは (2, 1, 2, 1, 1, 1) になります。
参加者 3 が正解し、各参加者のポイントは (1, 0, 2, 0, 0, 0) になります。
参加者 2 が正解し、各参加者のポイントは (0, 0, 1, -1, -1, -1) になります。

得点が 0 以下になった参加者 1, 2, 4, 5, 6 は敗退し、残った参加者 3 が勝ち抜けます。

入力例 2

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes

入力例 3

出力例 3

No
No
No
No
Yes
No
No
No
Yes
No

Score: 300 points

Problem Statement

Takahashi has decided to hold fastest-finger-fast quiz games. Kizahashi, who is in charge of making the scoreboard, is struggling to write the program that manages the players' scores in a game, which proceeds as follows.

A game is played by N players, numbered 1 to N. At the beginning of a game, each player has K points.

When a player correctly answers a question, each of the other N-1 players receives minus one (-1) point. There is no other factor that affects the players' scores.

At the end of a game, the players with 0 points or lower are eliminated, and the remaining players survive.

In the last game, the players gave a total of Q correct answers, the i-th of which was given by Player A_i. For Kizahashi, write a program that determines whether each of the N players survived this game.

Constraints

All values in input are integers.
2 \leq N \leq 10^5
1 \leq K \leq 10^9
1 \leq Q \leq 10^5
1 \leq A_i \leq N\ (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N K Q
A_1
A_2
.
.
.
A_Q

Output

Print N lines. The i-th line should contain Yes if Player i survived the game, and No otherwise.

Sample Input 1

Sample Output 1

No
No
Yes
No
No
No

In the beginning, the players' scores are (3, 3, 3, 3, 3, 3).

Player 3 correctly answers a question. The players' scores are now (2, 2, 3, 2, 2, 2).
Player 1 correctly answers a question. The players' scores are now (2, 1, 2, 1, 1, 1).
Player 3 correctly answers a question. The players' scores are now (1, 0, 2, 0, 0, 0).
Player 2 correctly answers a question. The players' scores are now (0, 0, 1, -1, -1, -1).

Players 1, 2, 4, 5 and 6, who have 0 points or lower, are eliminated, and Player 3 survives this game.

Sample Input 2

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

Sample Output 3

No
No
No
No
Yes
No
No
No
Yes
No

D - Powerful Discount Tickets

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋くんは N 個の品物を 1 個ずつ順番に買う予定です。

i 番目に買う品物の値段は A_i 円です。

高橋くんは M 枚の割引券を持っています。

品物を買う際に割引券を好きな枚数使うことができます。

X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を \frac{X}{2^Y} 円(小数点以下切り捨て)で買うことができます。

最小で何円あれば全ての品物を買うことができるでしょうか。

制約

入力は全て整数である。
1 \leq N, M \leq 10^5
1 \leq A_i \leq 10^9

入力

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

N M
A_1 A_2 ... A_N

出力

全ての品物を買うのに必要なお金の最小値を出力せよ。

入力例 1

3 3
2 13 8

出力例 1

以下のように割引券を使えば、合計 9 円で全ての商品を買うことができます。

1 番目に買う品物には割引券を使わず、2 円で買います。
2 番目に買う品物には 2 枚の割引券を使い、3 円で買います。
3 番目に買う品物には 1 枚の割引券を使い、4 円で買います。

入力例 2

4 4
1 9 3 5

出力例 2

入力例 3

1 100000
1000000000

出力例 3

1000000000 円の品物を買う際に 100000 枚の割引券を使うと 0 円で買うことができます。

入力例 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 4

9500000000

Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A_i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.

What is the minimum amount of money required to buy all the items?

Constraints

All values in input are integers.
1 \leq N, M \leq 10^5
1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the minimum amount of money required to buy all the items.

Sample Input 1

3 3
2 13 8

Sample Output 1

We can buy all the items for 9 yen, as follows:

Buy the 1-st item for 2 yen without tickets.
Buy the 2-nd item for 3 yen with 2 tickets.
Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

Sample Input 3

1 100000
1000000000

Sample Output 3

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000

E - Who Says a Pun?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の文字列 S が与えられます。

非空文字列であって、S の連続する部分文字列として重ならずに 2 回以上現れるもののうち、最長のものの長さを答えてください。

より厳密には、

l_1 + len \leq l_2
S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

を満たす整数 l_1 , l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) が存在するような正整数 len の最大値を求めてください。そのような len が存在しないときは、0 を出力してください。

制約

2 ≤ N ≤ 5 \times 10^3
|S| = N
S は英小文字から成る

入力

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

N
S

出力

非空文字列であって、S の連続する部分文字列として重ならずに 2 回以上現れるもののうち、最長のものの長さを出力せよ。そのような非空文字列が存在しないときは、0 を出力せよ。

入力例 1

5
ababa

出力例 1

条件を満たす文字列として、a, b, ab, ba が考えられます。これらの長さの最大値 2 が答えです。 aba は S の連続する部分文字列として 2 度現れますが、l_1 + len \leq l_2 を満たすような l_1 , l_2 が取れないことに注意してください。

入力例 2

2
xy

出力例 2

条件を満たす非空文字列は存在しません。

入力例 3

13
strangeorange

出力例 3

Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2
S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3
|S| = N
S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer. Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

F - Xor Sum 3

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600 点

問題文

N 個の非負整数 A_1, A_2, ..., A_N があります。

このうち 1 個以上 N-1 個以下を赤色で、残りを青色で塗り分けることを考えます。

塗り分けの 美しさ を、「赤く塗った整数の \text{XOR}」と「青く塗った整数の \text{XOR}」の和とします。

塗り分けの美しさの最大値を求めてください。

\text{XOR} とは

n 個の非負整数 x_1,x_2, \ldots, x_n の \text{XOR} x_1 \oplus x_2 \oplus \ldots \oplus x_n は以下のように定義されます。

x_1 \oplus x_2 \oplus \ldots \oplus x_n を二進表記した際の 2^k(k \geq 0) の位の数は x_1,x_2, \ldots, x_n のうち、二進表記した際の 2^k(k \geq 0) の位の数が 1 となるものの個数が奇数ならば 1、そうでなければ 0 となる。

例えば、3 \oplus 5 = 6 となります。

制約

入力はすべて整数
2 \leq N \leq 10^5
0 \leq A_i < 2^{60}\ (1 \leq i \leq N)

入力

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

N
A_1 A_2 ... A_N

出力

塗り分けの美しさの最大値を出力してください。

入力例 1

3
3 6 5

出力例 1

(3, 6, 5) をそれぞれ (青, 赤, 青) で塗り分けたとき、美しさは (6) + (3 \oplus 5) = 12 になります。

12 よりも高い美しさの塗り分けは存在しないので、答えは 12 です。

入力例 2

4
23 36 66 65

出力例 2

入力例 3

20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

出力例 3

2012721721873704572

A_i や答えは 32 ビット整数型に収まらないことがあります。

Score: 600 points

Problem Statement

We have N non-negative integers: A_1, A_2, ..., A_N.

Consider painting at least one and at most N-1 integers among them in red, and painting the rest in blue.

Let the beauty of the painting be the \text{XOR} of the integers painted in red, plus the \text{XOR} of the integers painted in blue.

Find the maximum possible beauty of the painting.

What is \text{XOR}?

The bitwise \text{XOR} x_1 \oplus x_2 \oplus \ldots \oplus x_n of n non-negative integers x_1, x_2, \ldots, x_n is defined as follows:

When x_1 \oplus x_2 \oplus \ldots \oplus x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.

For example, 3 \oplus 5 = 6.

Constraints

All values in input are integers.
2 \leq N \leq 10^5
0 \leq A_i < 2^{60}\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible beauty of the painting.

Sample Input 1

3
3 6 5

Sample Output 1

If we paint 3, 6, 5 in blue, red, blue, respectively, the beauty will be (6) + (3 \oplus 5) = 12.

There is no way to paint the integers resulting in greater beauty than 12, so the answer is 12.

Sample Input 2

4
23 36 66 65

Sample Output 2

Sample Input 3

20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

Sample Output 3

2012721721873704572

A_i and the answer may not fit into a 32-bit integer type.