実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
高橋君の住む町の天気は、一日ごとに晴れ(Sunny
)、くもり(Cloudy
)、雨(Rainy
)、晴れ、くもり、雨、… と周期的に変化します。
今日の天気を表す文字列 S が与えられるので、明日の天気を予測してください。
制約
- S は
Sunny
,Cloudy
,Rainy
のいずれかである
入力
入力は以下の形式で標準入力から与えられる。
S
出力
明日の天気を入力と同じ形式で出力せよ。
入力例 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
, orRainy
.
Input
Input is given from Standard Input in the following format:
S
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
実行時間制限: 2 sec / メモリ制限: 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
出力
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
, orD
. - Every character in an even position (2-nd, 4-th, 6-th, \ldots) is
L
,U
, orD
.
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
, orD
.
Input
Input is given from Standard Input in the following format:
S
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
実行時間制限: 2 sec / メモリ制限: 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
6 3 4 3 1 3 2
出力例 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
6 5 4 3 1 3 2
出力例 2
Yes Yes Yes Yes Yes Yes
入力例 3
10 13 15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 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
6 3 4 3 1 3 2
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
6 5 4 3 1 3 2
Sample Output 2
Yes Yes Yes Yes Yes Yes
Sample Input 3
10 13 15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Sample Output 3
No No No No Yes No No No Yes No
実行時間制限: 2 sec / メモリ制限: 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
以下のように割引券を使えば、合計 9 円で全ての商品を買うことができます。
- 1 番目に買う品物には割引券を使わず、2 円で買います。
- 2 番目に買う品物には 2 枚の割引券を使い、3 円で買います。
- 3 番目に買う品物には 1 枚の割引券を使い、4 円で買います。
入力例 2
4 4 1 9 3 5
出力例 2
6
入力例 3
1 100000 1000000000
出力例 3
0
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
9
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
6
Sample Input 3
1 100000 1000000000
Sample Output 3
0
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
実行時間制限: 2 sec / メモリ制限: 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
2
条件を満たす文字列として、a
, b
, ab
, ba
が考えられます。これらの長さの最大値 2 が答えです。
aba
は S の連続する部分文字列として 2 度現れますが、l_1 + len \leq l_2 を満たすような l_1 , l_2 が取れないことに注意してください。
入力例 2
2 xy
出力例 2
0
条件を満たす非空文字列は存在しません。
入力例 3
13 strangeorange
出力例 3
5
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
2
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
0
No non-empty string satisfies the conditions.
Sample Input 3
13 strangeorange
Sample Output 3
5
実行時間制限: 2 sec / メモリ制限: 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 となる。
制約
- 入力はすべて整数
- 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
12
(3, 6, 5) をそれぞれ (青, 赤, 青) で塗り分けたとき、美しさは (6) + (3 \oplus 5) = 12 になります。
12 よりも高い美しさの塗り分けは存在しないので、答えは 12 です。
入力例 2
4 23 36 66 65
出力例 2
188
入力例 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.
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
12
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
188
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.