実行時間制限: 1 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
このコンテストの名前はCODEFESTIVAL
で、いくつかの文字を消すとCF
という文字列にすることが出来ます。
好奇心旺盛な高橋君は、他の文字列に対してもこのようにCF
を得られるか気になりました。
英大文字アルファベットからなる文字列sが与えられるので、sからいくつかの文字を消してCF
という文字列にすることが出来るか判定してください。
制約
- 2≦|s|≦100
- sは英大文字(
A
-Z
)のみからなる文字列である
入力
入力は以下の形式で標準入力から与えられる。
s
出力
sからいくつかの文字を消してCF
という文字列にすることが出来るならYes
を、そうでないならNo
を出力せよ。
入力例 1
CODEFESTIVAL
出力例 1
Yes
1文字目のC
と5文字目のF
を残して消すことでCF
が得られます。
入力例 2
FESTIVALCODE
出力例 2
No
FC
なら得ることが出来ますが、文字の順番を変えることは出来ないので、この場合はCF
を作ることが出来ません。
入力例 3
CF
出力例 3
Yes
一文字も消さないこともありえます。
入力例 4
FCF
出力例 4
Yes
1文字目を消すことで得られます。
Score : 100 points
Problem Statement
This contest is CODEFESTIVAL
, which can be shortened to the string CF
by deleting some characters.
Mr. Takahashi, full of curiosity, wondered if he could obtain CF
from other strings in the same way.
You are given a string s consisting of uppercase English letters.
Determine whether the string CF
can be obtained from the string s by deleting some characters.
Constraints
- 2 ≤ |s| ≤ 100
- All characters in s are uppercase English letters (
A
-Z
).
Input
The input is given from Standard Input in the following format:
s
Output
Print Yes
if the string CF
can be obtained from the string s by deleting some characters.
Otherwise print No
.
Sample Input 1
CODEFESTIVAL
Sample Output 1
Yes
CF
is obtained by deleting characters other than the first character C
and the fifth character F
.
Sample Input 2
FESTIVALCODE
Sample Output 2
No
FC
can be obtained but CF
cannot be obtained because you cannot change the order of the characters.
Sample Input 3
CF
Sample Output 3
Yes
It is also possible not to delete any characters.
Sample Input 4
FCF
Sample Output 4
Yes
CF
is obtained by deleting the first character.
実行時間制限: 1 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
K 個のケーキがあります。高橋君は、1日に一つずつ、K 日かけてこれらのケーキを食べようと考えています。
ケーキはT 種類あり、種類i (1≦i≦T) のケーキはa_i 個あります。
二日連続で同じ種類のケーキを食べると飽きてしまうため、高橋君は、うまくケーキを食べる順番を決めて、前日と同じ種類のケーキを食べる日数を最小にしようと考えました。
高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。
制約
- 1≦K≦10000, 1≦T≦100
- 1≦a_i≦100
- a_1+a_2+ ... +a_T = K
入力
入力は以下の形式で標準入力から与えられる。
K T a_1 a_2 ... a_T
出力
前日と同じ種類のケーキを食べる日数の最小値を出力せよ。
入力例 1
7 3 3 2 2
出力例 1
0
ケーキは7個あります。例えば種類2,1,2,3,1,3,1の順で食べると一度も前日と同じ種類のケーキを食べなくてすみます。
入力例 2
6 3 1 4 1
出力例 2
1
ケーキは6個あります。種類2,3,2,2,1,2の順で食べると4日目だけ前日と同じ種類2のケーキを食べることになり、これが最小になるので答えは1です。
入力例 3
100 1 100
出力例 3
99
高橋君は一種類のケーキしか持っていないため、2日目以降は毎日前日と同じ種類のケーキを食べるしかありません。
Score : 200 points
Problem Statement
There are K pieces of cakes. Mr. Takahashi would like to eat one cake per day, taking K days to eat them all.
There are T types of cake, and the number of the cakes of type i (1 ≤ i ≤ T) is a_i.
Eating the same type of cake two days in a row would be no fun, so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.
Compute the minimum number of days on which the same type of cake as the previous day will be eaten.
Constraints
- 1 ≤ K ≤ 10000
- 1 ≤ T ≤ 100
- 1 ≤ a_i ≤ 100
- a_1 + a_2 + ... + a_T = K
Input
The input is given from Standard Input in the following format:
K T a_1 a_2 ... a_T
Output
Print the minimum number of days on which the same type of cake as the previous day will be eaten.
Sample Input 1
7 3 3 2 2
Sample Output 1
0
For example, if Mr. Takahashi eats cakes in the order of 2, 1, 2, 3, 1, 3, 1, he can avoid eating the same type of cake as the previous day.
Sample Input 2
6 3 1 4 1
Sample Output 2
1
There are 6 cakes. For example, if Mr. Takahashi eats cakes in the order of 2, 3, 2, 2, 1, 2, he has to eat the same type of cake (i.e., type 2) as the previous day only on the fourth day. Since this is the minimum number, the answer is 1.
Sample Input 3
100 1 100
Sample Output 3
99
Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。この山脈はN 個の山からなっており、西から東に向けて山1,山2,...,山Nと一直線に並んでいます。高橋君は西から、青木君は東からこの山脈を踏破しました。
山i の高さはh_i ですが、二人とも各h_i の値は忘れてしまいました。その代わり、各i (1≦i≦N) に対して、山i の山頂にたどり着いた時の、それまでに登った山(山i も含む)の高さの最大値を記録しています。 高橋君の記録した値はT_i で、青木君の記録した値はA_i です。
各山の高さh_i が正の整数であることはわかっています。山の高さの列としてありうるものが何通りあるかを10^9+7 で割ったあまりを求めてください。
ただし記録が間違っていてありうる山の高さの列が存在しないこともあります。この場合は0を出力してください。
制約
- 1≦N≦10^5
- 1≦T_i≦10^9
- 1≦A_i≦10^9
- T_i≦T_{i+1} (1≦i≦N-1)
- A_i≧A_{i+1} (1≦i≦N-1)
入力
入力は以下の形式で標準入力から与えられる。
N T_1 T_2 ... T_N A_1 A_2 ... A_N
出力
山の高さの列としてありうるものが何通りあるかを 10^9+7 で割ったあまりを出力せよ。
入力例 1
5 1 3 3 3 3 3 3 2 2 2
出力例 1
4
山の高さの列として、
- 1,3,2,2,2
- 1,3,2,1,2
- 1,3,1,2,2
- 1,3,1,1,2
の4通りがありえます。
入力例 2
5 1 1 1 2 2 3 2 1 1 1
出力例 2
0
高橋君によると山を全て登り切った後の山の高さの最大値は2で、青木君によると3なので、記録は矛盾しています。
入力例 3
10 1 3776 3776 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 3776 5
出力例 3
884111967
10^9+7 で割ったあまりを求めることを忘れないようにしてください。
入力例 4
1 17 17
出力例 4
1
山が一つの山脈もあります。
Score : 400 points
Problem Statement
Mountaineers Mr. Takahashi and Mr. Aoki recently trekked across a certain famous mountain range. The mountain range consists of N mountains, extending from west to east in a straight line as Mt. 1, Mt. 2, ..., Mt. N. Mr. Takahashi traversed the range from the west and Mr. Aoki from the east.
The height of Mt. i is h_i, but they have forgotten the value of each h_i. Instead, for each i (1 ≤ i ≤ N), they recorded the maximum height of the mountains climbed up to the time they reached the peak of Mt. i (including Mt. i). Mr. Takahashi's record is T_i and Mr. Aoki's record is A_i.
We know that the height of each mountain h_i is a positive integer. Compute the number of the possible sequences of the mountains' heights, modulo 10^9 + 7.
Note that the records may be incorrect and thus there may be no possible sequence of the mountains' heights. In such a case, output 0.
Constraints
- 1 ≤ N ≤ 10^5
- 1 ≤ T_i ≤ 10^9
- 1 ≤ A_i ≤ 10^9
- T_i ≤ T_{i+1} (1 ≤ i ≤ N - 1)
- A_i ≥ A_{i+1} (1 ≤ i ≤ N - 1)
Input
The input is given from Standard Input in the following format:
N T_1 T_2 ... T_N A_1 A_2 ... A_N
Output
Print the number of possible sequences of the mountains' heights, modulo 10^9 + 7.
Sample Input 1
5 1 3 3 3 3 3 3 2 2 2
Sample Output 1
4
The possible sequences of the mountains' heights are:
- 1, 3, 2, 2, 2
- 1, 3, 2, 1, 2
- 1, 3, 1, 2, 2
- 1, 3, 1, 1, 2
for a total of four sequences.
Sample Input 2
5 1 1 1 2 2 3 2 1 1 1
Sample Output 2
0
The records are contradictory, since Mr. Takahashi recorded 2 as the highest peak after climbing all the mountains but Mr. Aoki recorded 3.
Sample Input 3
10 1 3776 3776 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 8848 3776 5
Sample Output 3
884111967
Don't forget to compute the number modulo 10^9 + 7.
Sample Input 4
1 17 17
Sample Output 4
1
Some mountain ranges consist of only one mountain.
実行時間制限: 2 sec / メモリ制限: 512 MB
配点 : 800 点
問題文
高橋君の部屋には縦 H 行、横 W 列、 H \times W 個のブロックからなるオブジェがあります。
各ブロックには色がついています。色は英小文字(a
-z
) で表されます。上から i 個目、左から j 個目のブロックの色は c_{i,j} です。
あまり見栄えが良くないため高橋君はこのオブジェを解体しようとしています。解体作業は以下の操作の繰り返しになります。
- W 個の列のうち一つを選び、その列を一段沈める。その列の一番下にあったブロックは消滅する。
同じ色のブロックは引き寄せ合う力を持つため、この操作にかかるコストは、「選んだ列のブロックと(操作前に)横に隣り合っているブロックで、色が同じもの の個数」になります。
高橋君はこの作業を H \times W 回行うことで全てのブロックを消滅させオブジェを解体します。操作する列の順番をうまく選ぶことによって、解体にかかるコストの総和を最小化してください。
制約
- 1≦H≦300
- 2≦W≦300
- c_{i,j} は英小文字(
a
-z
)
部分点
- W=3 を満たすデータセットに正解すると、300 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
H W c_{1,1}c_{1,2}..c_{1,W} c_{2,1}c_{2,2}..c_{2,W} : c_{H,1}c_{H,2}..c_{H,W}
出力
解体にかかるコストの総和の最小値を出力せよ。
入力例 1
2 3 rrr brg
出力例 1
2
例えば下図のような順で操作するとコストの総和は 2 に出来て、これが最小値です。
入力例 2
6 3 xya xya ayz ayz xaz xaz
出力例 2
0
はじめに真ん中の列を全て沈め、次に左の列を全て沈め、最後に右の列を全て沈めることでコスト0を達成できます。
入力例 3
4 2 ay xa xy ay
出力例 3
0
右の列を一段沈める→左の列を一段沈める→右の段を全て沈める→左の段を全て沈める とすることでコスト0にすることが可能です。
入力例 4
5 5 aaaaa abbba ababa abbba aaaaa
出力例 4
24
入力例 5
7 10 xxxxxxxxxx ccccxxffff cxxcxxfxxx cxxxxxffff cxxcxxfxxx ccccxxfxxx xxxxxxxxxx
出力例 5
130
Score : 800 points
Problem Statement
Mr. Takahashi has in his room an art object with H rows and W columns, made up of H \times W blocks.
Each block has a color represented by a lowercase English letter (a
-z
).
The color of the block at the i-th row and j-th column is c_{i,j}.
Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes. The dismantling is processed by repeating the following operation:
- Choose one of the W columns and push down that column one row. The block at the bottom of that column disappears.
Each time the operation is performed, a cost is incurred. Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks (p, q) such that:
- The block p is in the selected column.
- The two blocks p and q are horizontally adjacent (before pushing down the column).
- The two blocks p and q have the same color.
Mr. Takahashi dismantles the object by repeating the operation H \times W times to get rid of all the blocks. Compute the minimum total cost to dismantle the object.
Constraints
- 1 ≤ H ≤ 300
- 2 ≤ W ≤ 300
- All characters c_{i,j} are lowercase English letters (
a
-z
).
Partial Score
- In test cases worth 300 points, W = 3.
Input
The input is given from Standard Input in the following format:
H W c_{1,1}c_{1,2}..c_{1,W} c_{2,1}c_{2,2}..c_{2,W} : c_{H,1}c_{H,2}..c_{H,W}
Output
Print the minimum total cost to dismantle the object.
Sample Input 1
2 3 rrr brg
Sample Output 1
2
For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.
Sample Input 2
6 3 xya xya ayz ayz xaz xaz
Sample Output 2
0
The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.
Sample Input 3
4 2 ay xa xy ay
Sample Output 3
0
The total cost of 0 can be achieved by the following operations:
- pushing down the right column one row;
- pushing down the left column one row;
- pushing down all of the right column;
- and pushing down all of the left column.
Sample Input 4
5 5 aaaaa abbba ababa abbba aaaaa
Sample Output 4
24
Sample Input 5
7 10 xxxxxxxxxx ccccxxffff cxxcxxfxxx cxxxxxffff cxxcxxfxxx ccccxxfxxx xxxxxxxxxx
Sample Output 5
130
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1200 点
問題文
ある日高橋君は、1~N からなる N! 個の順列全てが載っている辞書を拾いました。辞書は N! ページからなり、 i (1≦i≦N!) ページ目には辞書順 i 番目の順列が載っています。高橋君はこの辞書で長さ N のある順列を調べようとしましたが、順列の一部の数は忘れてしまいました。そのため、可能性のある順列全てをこの辞書で調べようとしています。高橋くんが調べる必要のあるページ番号の総和を 10^9+7 で割ったあまりを求めてください。
順列の情報は P_1,P_2,...,P_N で与えられます。P_i=0 の時は順列の i 番目の数を忘れてしまったことを、そうでない場合は順列の i 番目の数が P_i であることを意味します。
制約
- 1≦N≦500000
- 0≦P_i≦N
- i≠j (1≦i,j≦N) かつ P_i≠0 かつ P_j≠0 ならば、 P_i≠P_j
部分点
- 1≦N≦3000 を満たすデータセットに正解すると、500 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 ... P_N
出力
高橋くんが調べる必要のあるページ番号の総和を 10^9+7 で割ったあまりを出力せよ。
入力例 1
4 0 2 3 0
出力例 1
23
ありうる順列は[1,2,3,4]と[4,2,3,1]です。前者は1ページ目に、後者は22ページ目に載っているため、答えは23です。
入力例 2
3 0 0 0
出力例 2
21
長さ3の全ての順列がありうるので、答えは1+2+3+4+5+6 = 21 になります。
入力例 3
5 1 2 3 5 4
出力例 3
2
高橋君は完全に順列を記憶しています。
入力例 4
1 0
出力例 4
1
辞書は1ページからなります。
入力例 5
10 0 3 0 0 1 0 4 0 0 0
出力例 5
953330050
Score : 1200 points
Problem Statement
One day Mr. Takahashi picked up a dictionary containing all of the N! permutations of integers 1 through N. The dictionary has N! pages, and page i (1 ≤ i ≤ N!) contains the i-th permutation in the lexicographical order.
Mr. Takahashi wanted to look up a certain permutation of length N in this dictionary, but he forgot some part of it.
His memory of the permutation is described by a sequence P_1, P_2, ..., P_N. If P_i = 0, it means that he forgot the i-th element of the permutation; otherwise, it means that he remembered the i-th element of the permutation and it is P_i.
He decided to look up all the possible permutations in the dictionary. Compute the sum of the page numbers of the pages he has to check, modulo 10^9 + 7.
Constraints
- 1 ≤ N ≤ 500000
- 0 ≤ P_i ≤ N
- P_i ≠ P_j if i ≠ j (1 ≤ i, j ≤ N), P_i ≠ 0 and P_j ≠ 0.
Partial Score
- In test cases worth 500 points, 1 ≤ N ≤ 3000.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 ... P_N
Output
Print the sum of the page numbers of the pages he has to check, as modulo 10^9 + 7.
Sample Input 1
4 0 2 3 0
Sample Output 1
23
The possible permutations are [1, 2, 3, 4] and [4, 2, 3, 1]. Since the former is on page 1 and the latter is on page 22, the answer is 23.
Sample Input 2
3 0 0 0
Sample Output 2
21
Since all permutations of length 3 are possible, the answer is 1 + 2 + 3 + 4 + 5 + 6 = 21.
Sample Input 3
5 1 2 3 5 4
Sample Output 3
2
Mr. Takahashi remembered all the elements of the permutation.
Sample Input 4
1 0
Sample Output 4
1
The dictionary consists of one page.
Sample Input 5
10 0 3 0 0 1 0 4 0 0 0
Sample Output 5
953330050