Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
りんごさんは、とある祭りに参加しようとしています。
その祭りの名称が FESTIVAL
で終わる文字列 S として入力に与えられるので、りんごさんが何の祭りに参加しようしているのかを出力して下さい。
ただし、s の祭りの名称は s の末尾に FESTIVAL
を 1 つだけ追加した文字列であるとします。
例えば CODEFESTIVAL
は CODE
の祭りです。
制約
- 9 \leq |S| \leq 50
- S は大文字アルファベットのみからなる
- S は
FESTIVAL
で終わる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
りんごさんが何の祭りに参加しようしているのかを出力せよ。
入力例 1
CODEFESTIVAL
出力例 1
CODE
問題文中の例の通りです。
入力例 2
CODEFESTIVALFESTIVAL
出力例 2
CODEFESTIVAL
CODEFESTIVAL
の末尾に FESTIVAL
を追加した文字列であるので、これは CODEFESTIVAL
の祭りとなります。
入力例 3
YAKINIKUFESTIVAL
出力例 3
YAKINIKU
Score : 100 points
Problem Statement
Rng is going to a festival.
The name of the festival is given to you as a string S, which ends with FESTIVAL
, from input. Answer the question: "Rng is going to a festival of what?" Output the answer.
Here, assume that the name of "a festival of s" is a string obtained by appending FESTIVAL
to the end of s.
For example, CODEFESTIVAL
is a festival of CODE
.
Constraints
- 9 \leq |S| \leq 50
- S consists of uppercase English letters.
- S ends with
FESTIVAL
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer to the question: "Rng is going to a festival of what?"
Sample Input 1
CODEFESTIVAL
Sample Output 1
CODE
This is the same as the example in the statement.
Sample Input 2
CODEFESTIVALFESTIVAL
Sample Output 2
CODEFESTIVAL
This string is obtained by appending FESTIVAL
to the end of CODEFESTIVAL
, so it is a festival of CODEFESTIVAL
.
Sample Input 3
YAKINIKUFESTIVAL
Sample Output 3
YAKINIKU
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
りんごさんは CODEFESTIVAL の予選の問題セットを組もうとしています。
りんごさんは N 個の問題案を持っており、i 個目の問題案の難易度は D_i です。
予選の問題セットには M 問の問題が必要で、i 問目の問題に使う問題案の難易度はちょうど T_i でなければなりません。ただし、1 つの問題案を複数の問題に使うことはできません。
りんごさんが新しく問題案を作ることなく予選の問題セットを完成させることができるかを判定して下さい。
制約
- 1 \leq N \leq 200,000
- 1 \leq D_i \leq 10^9
- 1 \leq M \leq 200,000
- 1 \leq T_i \leq 10^9
- 入力される値は全て整数である
部分点
- N \leq 100 かつ M \leq 100 を満たすデータセットに正解した場合は、100 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N D_1 D_2 ... D_N M T_1 T_2 ... T_M
出力
りんごさんが新しく問題案を作ることなく予選の問題セットを完成させることができる場合は YES
、できない場合は NO
を出力せよ。
入力例 1
5 3 1 4 1 5 3 5 4 3
出力例 1
YES
入力例 2
7 100 200 500 700 1200 1600 2000 6 100 200 500 700 1600 1600
出力例 2
NO
この入力では、難易度 1600 の問題案が足りていません。
入力例 3
1 800 5 100 100 100 100 100
出力例 3
NO
入力例 4
15 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 9 5 4 3 2 1 2 3 4 5
出力例 4
YES
Score : 200 points
Problem Statement
Rng is preparing a problem set for a qualification round of CODEFESTIVAL.
He has N candidates of problems. The difficulty of the i-th candidate is D_i.
There must be M problems in the problem set, and the difficulty of the i-th problem must be T_i. Here, one candidate of a problem cannot be used as multiple problems.
Determine whether Rng can complete the problem set without creating new candidates of problems.
Constraints
- 1 \leq N \leq 200,000
- 1 \leq D_i \leq 10^9
- 1 \leq M \leq 200,000
- 1 \leq T_i \leq 10^9
- All numbers in the input are integers.
Partial Score
- 100 points will be awarded for passing the test set satisfying N \leq 100 and M \leq 100.
Input
Input is given from Standard Input in the following format:
N D_1 D_2 ... D_N M T_1 T_2 ... T_M
Output
Print YES
if Rng can complete the problem set without creating new candidates of problems; print NO
if he cannot.
Sample Input 1
5 3 1 4 1 5 3 5 4 3
Sample Output 1
YES
Sample Input 2
7 100 200 500 700 1200 1600 2000 6 100 200 500 700 1600 1600
Sample Output 2
NO
Not enough 1600s.
Sample Input 3
1 800 5 100 100 100 100 100
Sample Output 3
NO
Sample Input 4
15 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 9 5 4 3 2 1 2 3 4 5
Sample Output 4
YES
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
りんごさんは N 頂点 の連結な無向グラフを持っています。 このグラフにはすでに M 本の辺があり、i 本目の辺は頂点 A_i と頂点 B_i を繋いでいます。
りんごさんは以下の操作を行うことで、辺を追加しようと思っています。
- 操作:頂点 u から辺をちょうど 3 本辿ることによって頂点 v に辿り着けるような u,v (u \neq v) をとり、頂点 u と頂点 v の間に辺を追加する。ただし、すでに頂点 u と頂点 v の間に辺が存在する場合は辺を追加することはできない。
りんごさんが追加できる辺の本数の最大値を求めて下さい。
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i,B_i \leq N
- 多重辺や自己ループは存在しない
- 与えられるグラフは連結である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 : A_M B_M
出力
追加できる辺の本数の最大値を出力せよ。
入力例 1
6 5 1 2 2 3 3 4 4 5 5 6
出力例 1
4
下の図のように辺を追加していくと 4 本の辺を追加することができ、これ以上辺を追加することはできません。
入力例 2
5 5 1 2 2 3 3 1 5 4 5 1
出力例 2
5
例えば、以下のような順番で辺を追加することによって 5 本の辺を追加することができます。
- 頂点 5 と頂点 3 の間に辺を追加する。
- 頂点 5 と頂点 2 の間に辺を追加する。
- 頂点 4 と頂点 1 の間に辺を追加する。
- 頂点 4 と頂点 2 の間に辺を追加する。
- 頂点 4 と頂点 3 の間に辺を追加する。
Score : 500 points
Problem Statement
Rng has a connected undirected graph with N vertices. Currently, there are M edges in the graph, and the i-th edge connects Vertices A_i and B_i.
Rng will add new edges to the graph by repeating the following operation:
- Operation: Choose u and v (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.
Find the maximum possible number of edges that can be added.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i,B_i \leq N
- The graph has no self-loops or multiple edges.
- The graph is connected.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 : A_M B_M
Output
Find the maximum possible number of edges that can be added.
Sample Input 1
6 5 1 2 2 3 3 4 4 5 5 6
Sample Output 1
4
If we add edges as shown below, four edges can be added, and no more.
Sample Input 2
5 5 1 2 2 3 3 1 5 4 5 1
Sample Output 2
5
Five edges can be added, for example, as follows:
- Add an edge connecting Vertex 5 and Vertex 3.
- Add an edge connecting Vertex 5 and Vertex 2.
- Add an edge connecting Vertex 4 and Vertex 1.
- Add an edge connecting Vertex 4 and Vertex 2.
- Add an edge connecting Vertex 4 and Vertex 3.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
N 個のセルが一列に並んでいます。
何個かのセルはトークンを含んでいるかもしれません。
あなたは、 0
と 1
からなる文字列 s が与えられます。
s の i 文字目が 1
のとき、(左から) i 番目のセルはトークンを一個含んでいます。
そうでないとき、トークンを含んでいません。
すぬけ君は、以下の操作をできる限り行いたいです。 各操作では、三個の連続するセルを選びます。 セルを左から X, Y, Z とします。 操作を行うためには、 X と Z の両方がトークンを含み、 Y はトークンを含んでいてはなりません。 次に、すぬけ君はこれらの二個のトークンを取り除き、新しいトークンを Y に一個置きます。
最適な操作の方法をしたとき、すぬけ君は何回操作を行えますか?
制約
- 1 \leq N \leq 500,000
- |s| = N
- s の各文字は
0
または1
である。
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
答えを出力せよ。
入力例 1
7 1010101
出力例 1
2
例えば、以下の方法で操作を二回行うことができます:
- 最後の三個のセルに対し操作を行う。 トークンを表す文字列は
1010010
となる。 - 最初の三個のセルに対し操作を行う。 トークンを表す文字列は
0100010
となる。
操作の順番が重要であることに注意してください。 たとえば、最初に中央の三個のセルを選ぶと、それ以上操作を行えなくなります。
入力例 2
50 10101000010011011110001001111110000101010111100110
出力例 2
10
Score : 700 points
Problem Statement
N cells are arranged in a row.
Some of them may contain tokens.
You are given a string s that consists of 0
s and 1
s.
If the i-th character of s is 1
, the i-th cell (from left) contains a token.
Otherwise, it doesn't contain a token.
Snuke wants to perform the following operation as many times as possible. In each operation, he chooses three consecutive cells. Let's call the cells X, Y, Z from left to right. In order for the operation to be valid, both X and Z must contain tokens and Y must not contain a token. Then, he removes these two tokens and puts a new token on Y.
How many operations can he perform if he performs operations in the optimal way?
Constraints
- 1 \leq N \leq 500,000
- |s| = N
- Each character in s is either
0
or1
.
Input
Input is given from Standard Input in the following format:
N s
Output
Print the answer.
Sample Input 1
7 1010101
Sample Output 1
2
For example, he can perform two operations in the following way:
- Perform an operation on the last three cells. Now the string that represents tokens becomes
1010010
. - Perform an operation on the first three cells. Now the string that represents tokens becomes
0100010
.
Note that the choice of operations matters. For example, if he chooses three cells in the middle first, he can perform no more operations.
Sample Input 2
50 10101000010011011110001001111110000101010111100110
Sample Output 2
10
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
A + B 個のボールが一列に並べられています。 左から A 個のボールは赤で、右から B 個のボールは青で塗られています。
あなたは、以下の操作を行います:
- 最初に、 1 \leq s, t \leq A + B を満たす整数 s, t を選びます。
- 次に、以下のステップを A + B 回繰り返します: 各ステップでは、あなたは左から 1 番目または s 番目 (存在すれば) または t 番目 (存在すれば、すべて 1-based) のボールを選び、すぬけ君にあげます。
すぬけ君に何通りの方法でボールをあげることができるでしょうか? Mod 10^9 + 7 で求めてください。
ここで、ある整数 k に対し、 k 番目にすぬけ君にあげるボールの色が異なるとき、二つの方法は異なるとみなします。 特に、 s, t の選択は関係ありません。 また、同じ色の二つのボールは区別しません。
制約
- 1 \leq A, B \leq 2000
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 3
出力例 1
20
3 個の赤いボールと 3 個の青いボールをあげる方法は 20 通りあります。 それらのすべての方法が可能であることが分かります。
以下は操作の例です (r
は赤を、 b
は青をあらわします):
- s = 3, t = 4 を選ぶ。
- 最初、列は
rrrbbb
となっています。 - 3 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はrrbbb
となっています。 - 4 番目のボール (
b
) を取り除きすぬけ君にあげます。 列はrrbb
となっています。 - 1 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はrbb
となっています。 - 3 番目のボール (
b
) を取り除きすぬけ君にあげます。 列はrb
となっています。 - 1 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はb
となっています。 - 1 番目のボール (
b
) を取り除きすぬけ君にあげます。 列は空になります。
この方法では、すぬけ君は rbrbrb
の順でボールを受け取ります。
入力例 2
4 4
出力例 2
67
4 個の赤いボールと 4 個の青いボールをあげる方法は 70 通りあります。
そのうち、 bbrrbrbr
, brbrbrbr
, brrbbrbr
だけが不可能です。
入力例 3
7 9
出力例 3
7772
入力例 4
1987 1789
出力例 4
456315553
Score : 1600 points
Problem Statement
A + B balls are arranged in a row. The leftmost A balls are colored red, and the rightmost B balls are colored blue.
You perform the following operation:
- First, you choose two integers s, t such that 1 \leq s, t \leq A + B.
- Then, you repeat the following step A + B times: In each step, you remove the first ball or the s-th ball (if it exists) or the t-th ball (if it exists, all indices are 1-based) from left in the row, and give it to Snuke.
In how many ways can you give the balls to Snuke? Compute the answer modulo 10^9 + 7.
Here, we consider two ways to be different if for some k, the k-th ball given to Snuke has different colors. In particular, the choice of s, t doesn't matter. Also, we don't distinguish two balls of the same color.
Constraints
- 1 \leq A, B \leq 2000
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 3
Sample Output 1
20
There are 20 ways to give 3 red balls and 3 blue balls. It turns out that all of them are possible.
Here is an example of the operation (r
stands for red, b
stands for blue):
- You choose s = 3, t = 4.
- Initially, the row looks like
rrrbbb
. - You remove 3rd ball (
r
) and give it to Snuke. Now the row looks likerrbbb
. - You remove 4th ball (
b
) and give it to Snuke. Now the row looks likerrbb
. - You remove 1st ball (
r
) and give it to Snuke. Now the row looks likerbb
. - You remove 3rd ball (
b
) and give it to Snuke. Now the row looks likerb
. - You remove 1st ball (
r
) and give it to Snuke. Now the row looks likeb
. - You remove 1st ball (
b
) and give it to Snuke. Now the row is empty.
This way, Snuke receives balls in the order rbrbrb
.
Sample Input 2
4 4
Sample Output 2
67
There are 70 ways to give 4 red balls and 4 blue balls.
Among them, only bbrrbrbr
, brbrbrbr
, and brrbbrbr
are impossible.
Sample Input 3
7 9
Sample Output 3
7772
Sample Input 4
1987 1789
Sample Output 4
456315553
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
文字列 S に対し、 f(S) を S の巡回シフトのうち辞書順最小のものとします。
たとえば、 S = babca
のとき、 S の巡回シフト (babca
, abcab
, bcaba
, cabab
, ababc
) のうち最小の ababc
が f(S) となります。
あなたは、三個の整数 X, Y, Z が与えられます。
あなたは、 a
をちょうど X 個、b
をちょうど Y 個、c
をちょうど Z 個含む文字列 T を構成したいです。
そのような文字列が複数存在する場合は、 f(T) を辞書順で最大化したいです。
f(T) の辞書順での最大値を求めてください。
制約
- 1 \leq X + Y + Z \leq 50
- X, Y, Z は非負整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
答えを出力せよ。
入力例 1
2 2 0
出力例 1
abab
T は a
二個と b
二個からならなければなりません。
- T =
aabb
のとき f(T) =aabb
. - T =
abab
のとき f(T) =abab
. - T =
abba
のとき f(T) =aabb
. - T =
baab
のとき f(T) =aabb
. - T =
baba
のとき f(T) =abab
. - T =
bbaa
のとき f(T) =aabb
.
となるので、 f(T) の最大値は abab
です。
入力例 2
1 1 1
出力例 2
acb
Score : 1600 points
Problem Statement
For a string S, let f(S) be the lexicographically smallest cyclic shift of S.
For example, if S = babca
, f(S) = ababc
because this is the smallest among all cyclic shifts (babca
, abcab
, bcaba
, cabab
, ababc
).
You are given three integers X, Y, and Z.
You want to construct a string T that consists of exactly X a
s, exactly Y b
s, and exactly Z c
s.
If there are multiple such strings, you want to choose one that maximizes f(T) lexicographically.
Compute the lexicographically largest possible value of f(T).
Constraints
- 1 \leq X + Y + Z \leq 50
- X, Y, Z are non-negative integers.
Input
Input is given from Standard Input in the following format:
X Y Z
Output
Print the answer.
Sample Input 1
2 2 0
Sample Output 1
abab
T must consist of two a
s and two b
s.
- If T =
aabb
, f(T) =aabb
. - If T =
abab
, f(T) =abab
. - If T =
abba
, f(T) =aabb
. - If T =
baab
, f(T) =aabb
. - If T =
baba
, f(T) =abab
. - If T =
bbaa
, f(T) =aabb
.
Thus, the largest possible f(T) is abab
.
Sample Input 2
1 1 1
Sample Output 2
acb