Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる長さ 1 以上 25 以下の文字列 S が与えられます。
S に含まれない英小文字をひとつ出力してください。
但し、そのようなものが複数ある場合はどれを出力しても構いません。
制約
- S は英小文字からなる長さ 1 以上 25 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に含まれない英小文字をひとつ出力せよ。そのようなものが複数ある場合はどれを出力しても構わない。
入力例 1
a
出力例 1
d
S= a です。
a 以外の英小文字、 b, c, ..., z が正解となります。
入力例 2
abcdfhijklmnopqrstuvwxyz
出力例 2
e
S 中に含まれない英小文字は e と g です。
入力例 3
qazplwsxokmedcijnrfvuhbgt
出力例 3
y
Score : 100 points
Problem Statement
You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.
Constraints
- S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Output one lowercase English letter that does not appear in S. If there are multiple such letters, you may output any one of them.
Sample Input 1
a
Sample Output 1
d
S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.
Sample Input 2
abcdfhijklmnopqrstuvwxyz
Sample Output 2
e
The lowercase English letters not included in S are e and g.
Sample Input 3
qazplwsxokmedcijnrfvuhbgt
Sample Output 3
y
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
チーム高橋とチーム青木が、チーム高橋を先攻として野球を行なっています。
現在、9 回表までが終了し、9 回裏が始まろうとしています。
試合において、チーム高橋は i 回表 (1\leq i\leq 9) に A_i 点を取り、チーム青木は j 回裏 (1\leq j\leq 8) に B_j 点を取りました。
ここで、9 回表の終了時点でチーム高橋の得点はチーム青木の得点以上です。
チーム青木は 9 回裏に最低何点取れば勝利することができるか求めてください。
ただし、9 回裏の終了時点で同点であった場合は引き分けとなり、すなわちチーム青木が勝利するためには 9 回裏の終了時点でチーム高橋より真に多くの点をとっている必要があるものとします。
なお、（ある時点における）チーム高橋の得点はそれまでの回の表に取った点数の合計であり、チーム青木の得点はそれまでの回の裏に取った点数の合計です。
制約
- 0\leq A_i, B_j\leq 99
- A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8
出力
チーム青木が勝利するために 9 回裏に取る必要のある最小の得点を出力せよ。
入力例 1
0 1 0 1 2 2 0 0 1 1 1 0 0 0 0 1 0
出力例 1
5
9 回表の終了時点でチーム高橋の得点は 7 点、チーム青木の得点は 3 点となっています。
よって、チーム青木は9 回裏に 5 点取れば 7-8 となり、勝利することができます。
9 回裏に 4 点では、引き分けとなり勝利できないことに注意してください。
入力例 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 2
1
Score: 100 points
Problem Statement
Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.
Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.
Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.
Constraints
- 0\leq A_i, B_j\leq 99
- A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8
Output
Print the minimum number of runs Team Aoki needs to score in the bottom of the ninth inning to win.
Sample Input 1
0 1 0 1 2 2 0 0 1 1 1 0 0 0 0 1 0
Sample Output 1
5
At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.
Sample Input 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
英小文字と ? からなる文字列 T と、英小文字のみからなる文字列 U が与えられます。
T は、英小文字のみからなる文字列 S のちょうど 4 文字を ? で置き換えることで得られた文字列です。
S が U を連続部分文字列として含んでいた可能性があるかどうか判定してください。
制約
- T は長さ 4 以上 10 以下の英小文字と
?からなる文字列 - T にはちょうど 4 つの
?が含まれる - U は長さ 1 以上 |T| 以下の英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
T U
出力
S が U を部分文字列として含んでいた可能性があるならば Yes を、そうでないならば No を出力せよ。
入力例 1
tak??a?h? nashi
出力例 1
Yes
例えば、S が takanashi である場合、これは nashi を連続部分文字列として含みます。
入力例 2
??e??e snuke
出力例 2
No
? がどのような文字であっても、S は snuke を連続部分文字列として含むことがありません。
入力例 3
???? aoki
出力例 3
Yes
Score : 250 points
Problem Statement
You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.
The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.
Determine whether it is possible that the original string S contained U as a contiguous substring.
Constraints
- T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and
?. - T contains exactly four occurrences of
?. - U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.
Input
The input is given from Standard Input in the following format:
T U
Output
Print Yes if it is possible that the original string S contained U as a contiguous substring; otherwise, print No.
Sample Input 1
tak??a?h? nashi
Sample Output 1
Yes
For example, if S is takanashi, it contains nashi as a contiguous substring.
Sample Input 2
??e??e snuke
Sample Output 2
No
No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.
Sample Input 3
???? aoki
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 商店には N 個の商品があります。 i\ (1\leq i\leq N) 番目の商品の価格は P _ i です。 i\ (1\leq i\leq N) 番目の商品は C _ i 個の機能をもち、i\ (1\leq i\leq N) 番目の商品の j\ (1\leq j\leq C _ i) 番目の機能は 1 以上 M 以下の整数 F _ {i,j} として表されます。
高橋くんは、AtCoder 商店の商品で一方が一方の上位互換であるものがないか気になりました。
i 番目の商品と j 番目の商品 (1\leq i,j\leq N) であって、次の条件をすべて満たすものがあるとき Yes と、ないとき No と出力してください。
- P _ i\geq P _ j である。
- j 番目の製品は i 番目の製品がもつ機能をすべてもつ。
- P _ i\gt P _ j であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ。
制約
- 2\leq N\leq100
- 1\leq M\leq100
- 1\leq P _ i\leq10^5\ (1\leq i\leq N)
- 1\leq C _ i\leq M\ (1\leq i\leq N)
- 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}
出力
答えを 1 行で出力せよ。
入力例 1
5 6 10000 2 1 3 15000 3 1 2 4 30000 3 1 3 5 35000 2 1 5 100000 6 1 2 3 4 5 6
出力例 1
Yes
(i,j)=(4,3) とすると、条件を全て満たします。
他の組は条件を満たしません。例えば (i,j)=(4,5) とすると j 番目の商品は i 番目の商品の機能をすべてもっていますが、P _ i\lt P _ j なので上位互換ではありません。
入力例 2
4 4 3 1 1 3 1 2 3 1 2 4 2 2 3
出力例 2
No
まったく同じ価格と機能をもった商品がある場合もあります。
入力例 3
20 10 72036 3 3 4 9 7716 4 1 2 3 6 54093 5 1 6 7 8 10 25517 7 3 4 5 6 7 9 10 96930 8 2 3 4 6 7 8 9 10 47774 6 2 4 5 6 7 9 36959 5 1 3 4 5 8 46622 7 1 2 3 5 6 8 10 34315 9 1 3 4 5 6 7 8 9 10 54129 7 1 3 4 6 7 8 9 4274 5 2 4 7 9 10 16578 5 2 3 6 7 9 61809 4 1 2 4 5 1659 5 3 5 6 9 10 59183 5 1 2 3 4 9 22186 4 3 5 6 8 98282 4 1 4 7 10 72865 8 1 2 3 4 6 8 9 10 33796 6 1 3 5 7 9 10 74670 4 1 2 6 8
出力例 3
Yes
Score : 200 points
Problem Statement
AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.
Takahashi wonders whether there is a product that is strictly superior to another.
If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.
- P _ i\geq P _ j.
- The j-th product has all functions of the i-th product.
- P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.
Constraints
- 2\leq N\leq100
- 1\leq M\leq100
- 1\leq P _ i\leq10^5\ (1\leq i\leq N)
- 1\leq C _ i\leq M\ (1\leq i\leq N)
- 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}
Output
Print the answer in a single line.
Sample Input 1
5 6 10000 2 1 3 15000 3 1 2 4 30000 3 1 3 5 35000 2 1 5 100000 6 1 2 3 4 5 6
Sample Output 1
Yes
(i,j)=(4,3) satisfies all of the conditions.
No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.
Sample Input 2
4 4 3 1 1 3 1 2 3 1 2 4 2 2 3
Sample Output 2
No
Multiple products may have the same price and functions.
Sample Input 3
20 10 72036 3 3 4 9 7716 4 1 2 3 6 54093 5 1 6 7 8 10 25517 7 3 4 5 6 7 9 10 96930 8 2 3 4 6 7 8 9 10 47774 6 2 4 5 6 7 9 36959 5 1 3 4 5 8 46622 7 1 2 3 5 6 8 10 34315 9 1 3 4 5 6 7 8 9 10 54129 7 1 3 4 6 7 8 9 4274 5 2 4 7 9 10 16578 5 2 3 6 7 9 61809 4 1 2 4 5 1659 5 3 5 6 9 10 59183 5 1 2 3 4 9 22186 4 3 5 6 8 98282 4 1 4 7 10 72865 8 1 2 3 4 6 8 9 10 33796 6 1 3 5 7 9 10 74670 4 1 2 6 8
Sample Output 3
Yes
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は全 10^9 巻の漫画『すぬけ君』を読むことにしました。
初め、高橋君は『すぬけ君』の単行本を N 冊持っています。i 番目の単行本は a_i 巻です。
高橋君は『すぬけ君』を読み始める前に限り次の操作を 0 回以上何度でも繰り返せます。
- 現在持っている単行本が 1 冊以下の場合、何もしない。そうでない場合、現在持っている単行本から 2 冊を選んで売り、代わりに好きな巻を選んで 1 冊買う
その後、高橋君は『すぬけ君』を 1 巻、2 巻、3 巻、\ldots と順番に読みます。ただし、次に読むべき巻を持っていない状態になった場合、(他の巻を持っているかどうかに関わらず)その時点で『すぬけ君』を読むのをやめます。
高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、1 巻を読めない場合の答えは 0 とします。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq a_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 2 4 6 7 271
出力例 1
4
『すぬけ君』を読み始める前に「7 巻と 271 巻を選んで売り、代わりに 3 巻を選んで 1 冊買う」という内容で操作をすると、高橋君は 1 巻、2 巻、3 巻、4 巻、6 巻を 1 冊ずつ持っている状態になります。
この状態から『すぬけ君』を読み始めると、高橋君は 1 巻、2 巻、3 巻、4 巻を読み、続いて 5 巻を読もうとしますが持っていないためこの時点で『すぬけ君』を読むのをやめます。
操作の方法を変えても 5 巻を読むことは出来ないため、4 が答えです。
入力例 2
10 1 1 1 1 1 1 1 1 1 1
出力例 2
5
高橋君は同じ巻を 2 冊以上持っているかもしれません。
この入力に対しては以下のように 4 回操作をしてから『すぬけ君』を読み始めることで 5 巻まで読むことが出来、これが最大です。
- 1 巻を 2 冊選んで売り、代わりに 2 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 3 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 4 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 5 巻を選んで 1 冊買う
入力例 3
1 5
出力例 3
0
高橋君は 1 巻を読めません。
Score : 300 points
Problem Statement
Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.
Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:
- Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.
Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).
Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 1 \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 a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 2 4 6 7 271
Sample Output 1
4
Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.
Sample Input 2
10 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:
- Sell two books of Volume 1 and buy a book of Volume 2 instead.
- Sell two books of Volume 1 and buy a book of Volume 3 instead.
- Sell two books of Volume 1 and buy a book of Volume 4 instead.
- Sell two books of Volume 1 and buy a book of Volume 5 instead.
Sample Input 3
1 5
Sample Output 3
0
Takahashi cannot read Volume 1.