Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
4 個の数字 N_1, N_2, N_3, N_4 が与えられます.これらを並べ替えて 1974 という数字の列を作ることが出来るかを判定してください.
制約
- 0 \leq N_1, N_2, N_3, N_4 \leq 9
- N_1, N_2, N_3, N_4 は整数
入力
入力は以下の形式で標準入力から与えられる.
N_1 N_2 N_3 N_4
出力
N_1, N_2, N_3, N_4 を並べ替えて 1974 という数字の列を作ることが出来るなら YES
を,出来ないなら NO
を出力せよ.
入力例 1
1 7 9 4
出力例 1
YES
N_2 と N_3 を入れ替えると 1974 となります.
入力例 2
1 9 7 4
出力例 2
YES
何もしなくても 1974 となっています.
入力例 3
1 2 9 1
出力例 3
NO
入力例 4
4 9 0 8
出力例 4
NO
Score : 100 points
Problem Statement
You are given four digits N_1, N_2, N_3 and N_4. Determine if these can be arranged into the sequence of digits "1974".
Constraints
- 0 \leq N_1, N_2, N_3, N_4 \leq 9
- N_1, N_2, N_3 and N_4 are integers.
Input
Input is given from Standard Input in the following format:
N_1 N_2 N_3 N_4
Output
If N_1, N_2, N_3 and N_4 can be arranged into the sequence of digits "1974", print YES
; if they cannot, print NO
.
Sample Input 1
1 7 9 4
Sample Output 1
YES
We can get 1974 by swapping N_2 and N_3.
Sample Input 2
1 9 7 4
Sample Output 2
YES
We already have 1974 before doing anything.
Sample Input 3
1 2 9 1
Sample Output 3
NO
Sample Input 4
4 9 0 8
Sample Output 4
NO
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
連続した部分文字列 (空でも良い) を 1 度だけ取り除くことで keyence
に変換することができる文字列をキーエンス型文字列と呼ぶことにします.
英小文字のみから成る文字列 S が与えられるので,S がキーエンス型文字列かどうか判定してください.
制約
- S の長さは 7 以上 100 以下
- S は英小文字のみから成る
入力
入力は以下の形式で標準入力から与えられる.
S
出力
S がキーエンス型文字列なら YES
を,そうでないなら NO
を出力せよ.
入力例 1
keyofscience
出力例 1
YES
keyence
とは key of science
の略です.
入力例 2
mpyszsbznf
出力例 2
NO
入力例 3
ashlfyha
出力例 3
NO
入力例 4
keyence
出力例 4
YES
Score : 200 points
Problem Statement
A string is called a KEYENCE string when it can be changed to keyence
by removing its contiguous substring (possibly empty) only once.
Given a string S consisting of lowercase English letters, determine if S is a KEYENCE string.
Constraints
- The length of S is between 7 and 100 (inclusive).
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
If S is a KEYENCE string, print YES
; otherwise, print NO
.
Sample Input 1
keyofscience
Sample Output 1
YES
keyence
is an abbreviation of key of science
.
Sample Input 2
mpyszsbznf
Sample Output 2
NO
Sample Input 3
ashlfyha
Sample Output 3
NO
Sample Input 4
keyence
Sample Output 4
YES
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
大学生の高橋君は N 個の試験を受けてすべてに合格する必要があります. 現在,i 番目の試験の準備度は A_{i} です. また,高橋君の入念な調査によって,i 番目の試験に合格するためには準備度を B_{i} 以上にしなくてはならないことが分かっています.
このままだとすべての試験に合格できないかもしれないと思った高橋君は,魔法使いの青木君に頼んで, 試験の準備度の総和は変えずに,なるべく少ない数の試験の準備度を変更してもらうことで試験を乗り切ることにしました.
高橋君に代わって,以下の条件を満たす数列 C_1, C_2, ..., C_{N} を考えたときの A_i と C_i が異なるような i の個数の最小値を求めてください. そのような数列 C_1, C_2, ..., C_{N} が構成できない場合は -1 を出力してください.
- 数列 A_1, A_2, ..., A_{N} の総和と数列 C_1, C_2, ..., C_{N} の総和は等しい
- どの i に対しても,B_i \leq C_i が成り立つ
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- A_i, B_i は整数
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 ... A_{N} B_1 B_2 ... B_{N}
出力
条件を満たす数列 C_1, C_2, ..., C_{N} を考えたときの A_i と C_i が異なるような i の個数の最小値を出力せよ. 数列 C_1, C_2, ..., C_{N} が構成できない場合は,-1 を出力せよ.
入力例 1
3 2 3 5 3 4 1
出力例 1
3
(A_1, A_2, A_3) = (2, 3, 5) ,(B_1, B_2, B_3) = (3, 4, 1) であり,このままでは 1 番目と 2 番目の試験に合格できません. 以下のように C_1, C_2, C_3 を構成すれば,A_i と C_i が異なるような i の個数の最小値 3 を達成できます.
- (C_1, C_2, C_3) = (3, 5, 2)
入力例 2
3 2 3 3 2 2 1
出力例 2
0
この場合は,何もしなくても全ての試験に合格できます.
入力例 3
3 17 7 1 25 6 14
出力例 3
-1
この場合は,どのようにしても全ての試験に合格することはできません.
入力例 4
12 757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604 74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212
出力例 4
5
Score : 400 points
Problem Statement
A university student, Takahashi, has to take N examinations and pass all of them. Currently, his readiness for the i-th examination is A_{i}, and according to his investigation, it is known that he needs readiness of at least B_{i} in order to pass the i-th examination.
Takahashi thinks that he may not be able to pass all the examinations, and he has decided to ask a magician, Aoki, to change the readiness for as few examinations as possible so that he can pass all of them, while not changing the total readiness.
For Takahashi, find the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the following conditions:
- The sum of the sequence A_1, A_2, ..., A_{N} and the sum of the sequence C_1, C_2, ..., C_{N} are equal.
- For every i, B_i \leq C_i holds.
If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- A_i and B_i are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_{N} B_1 B_2 ... B_{N}
Output
Print the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the conditions. If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.
Sample Input 1
3 2 3 5 3 4 1
Sample Output 1
3
(A_1, A_2, A_3) = (2, 3, 5) and (B_1, B_2, B_3) = (3, 4, 1). If nothing is done, he cannot pass the first and second exams. The minimum possible number of indices i such that A_i and C_i are different, 3, is achieved when:
- (C_1, C_2, C_3) = (3, 5, 2)
Sample Input 2
3 2 3 3 2 2 1
Sample Output 2
0
In this case, he has to do nothing in order to pass all the exams.
Sample Input 3
3 17 7 1 25 6 14
Sample Output 3
-1
In this case, no matter what is done, he cannot pass all the exams.
Sample Input 4
12 757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604 74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212
Sample Output 4
5
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 行 M 列のグリッドに,1 から N \times M までの整数を重複のないように 1 つずつ書き込むことを考えます. ここで,普通に書き込むのでは面白くないと思った高橋君は,以下の条件を満たすように数を書き込むことにしました.
- i 行目に書き込まれている値のうち,最大の値は A_i (1 \leq i \leq N)
- j 列目に書き込まれている値のうち,最大の値は B_j (1 \leq j \leq M)
高橋君のために,この条件を満たすような書き込み方の個数を 10^9 + 7 で割ったあまりを求めてください.
制約
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- 1 \leq A_i \leq N \times M
- 1 \leq B_j \leq N \times M
- A_i, B_j は整数
入力
入力は以下の形式で標準入力から与えられる.
N M A_1 A_2 ... A_{N} B_1 B_2 ... B_{M}
出力
条件を満たすような書き込み方の個数を 10^9 + 7 で割ったあまりを出力せよ.
入力例 1
2 2 4 3 3 4
出力例 1
2
(A_1, A_2) = (4, 3),(B_1, B_2) = (3, 4) であり,この場合は以下の 2 通りの書き込み方があります.
- 1 行 1 列目に 1,1 行 2 列目に 4,2 行 1 列目に 3,2 行 2 列目に 2
- 1 行 1 列目に 2,1 行 2 列目に 4,2 行 1 列目に 3,2 行 2 列目に 1
入力例 2
3 3 5 9 7 3 6 9
出力例 2
0
どのような書き込み方をしても条件を満たすことができないので,0 を出力します.
入力例 3
2 2 4 4 4 4
出力例 3
0
入力例 4
14 13 158 167 181 147 178 151 179 182 176 169 180 129 175 168 181 150 178 179 167 180 176 169 182 177 175 159 173
出力例 4
343772227
Score : 500 points
Problem Statement
Consider writing each of the integers from 1 to N \times M in a grid with N rows and M columns, without duplicates. Takahashi thinks it is not fun enough, and he will write the numbers under the following conditions:
- The largest among the values in the i-th row (1 \leq i \leq N) is A_i.
- The largest among the values in the j-th column (1 \leq j \leq M) is B_j.
For him, find the number of ways to write the numbers under these conditions, modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 1000
- 1 \leq M \leq 1000
- 1 \leq A_i \leq N \times M
- 1 \leq B_j \leq N \times M
- A_i and B_j are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_{N} B_1 B_2 ... B_{M}
Output
Print the number of ways to write the numbers under the conditions, modulo 10^9 + 7.
Sample Input 1
2 2 4 3 3 4
Sample Output 1
2
(A_1, A_2) = (4, 3) and (B_1, B_2) = (3, 4). In this case, there are two ways to write the numbers, as follows:
- 1 in (1, 1), 4 in (1, 2), 3 in (2, 1) and 2 in (2, 2).
- 2 in (1, 1), 4 in (1, 2), 3 in (2, 1) and 1 in (2, 2).
Here, (i, j) denotes the square at the i-th row and the j-th column.
Sample Input 2
3 3 5 9 7 3 6 9
Sample Output 2
0
Since there is no way to write the numbers under the condition, 0 should be printed.
Sample Input 3
2 2 4 4 4 4
Sample Output 3
0
Sample Input 4
14 13 158 167 181 147 178 151 179 182 176 169 180 129 175 168 181 150 178 179 167 180 176 169 182 177 175 159 173
Sample Output 4
343772227
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
AtCoder国には N 個の都市があります.i 番目の都市の規模は A_{i} です. 高橋君は,2 都市間を双方向に結ぶ道路を N-1 本建設することで N 個の都市のどの 2 つを取っても互いに道路を通り行き来できるようにしたいです.
i 番目の都市と j 番目の都市を結ぶ道路の建設コストが |i-j| \times D + A_{i} + A_{j} であるとします. 高橋君のために,目標を達成するためのコストの総和のあり得る最小値を求めてください.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- 1 \leq A_{i} \leq 10^9
- A_{i}, D は整数
入力
入力は以下の形式で標準入力から与えられる.
N D A_1 A_2 ... A_N
出力
コストの総和のあり得る最小値を出力せよ.
入力例 1
3 1 1 100 1
出力例 1
106
例えば,都市 1 と都市 2 の間と,都市 1 と都市 3 の間に道路を建設することで,このコストを達成することができます.
入力例 2
3 1000 1 100 1
出力例 2
2202
入力例 3
6 14 25 171 7 1 17 162
出力例 3
497
入力例 4
12 5 43 94 27 3 69 99 56 25 8 15 46 8
出力例 4
658
Score : 600 points
Problem Statement
There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}. Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.
Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}. For Takahashi, find the minimum possible total cost to achieve the objective.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- 1 \leq A_{i} \leq 10^9
- A_{i} and D are integers.
Input
Input is given from Standard Input in the following format:
N D A_1 A_2 ... A_N
Output
Print the minimum possible total cost.
Sample Input 1
3 1 1 100 1
Sample Output 1
106
This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.
Sample Input 2
3 1000 1 100 1
Sample Output 2
2202
Sample Input 3
6 14 25 171 7 1 17 162
Sample Output 3
497
Sample Input 4
12 5 43 94 27 3 69 99 56 25 8 15 46 8
Sample Output 4
658
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
縦の長さが H+1,横の長さが W+1 の長方形の紙が机に置かれています.xy 座標系を,紙の四隅の座標がそれぞれ (0, 0), (W + 1, 0), (0, H + 1), (W + 1, H + 1) となるように定めます.
この紙は,直線 x = 1,2,...,W と直線 y = 1,2,...,H に沿って切ることができます.これらの H + W 本の直線から K 本を選び,それらの直線に沿って何らかの順序で一回ずつ紙を切断していくという長さ K の操作列を考えます.
紙の 1 回の切断のスコアを,その直後の時点で存在する紙の破片の個数とします.操作列のスコアは,K 回すべての切断のスコアの和です.
考えられる全ての長さ K の操作列のスコアの和を計算してください.この値は非常に大きくなることがあるので,10^9 + 7 で割った余りを出力してください.
制約
- 1 \leq H,W \leq 10^7
- 1 \leq K \leq H + W
- H, W, K は整数
入力
入力は以下の形式で標準入力から与えられる.
H W K
出力
スコアの和を 10^9 + 7 で割った余りを出力せよ.
入力例 1
2 1 2
出力例 1
34
直線 x = 1 に沿った切断を x_1,直線 y = 1 に沿った切断を y_1,直線 y = 2 に沿った切断を y_2 と表記します.考えられる 6 通りの操作列とそれぞれのスコアは次の通りです.
- y_1, y_2: 2 + 3 = 5
- y_2, y_1: 2 + 3 = 5
- y_1, x_1: 2 + 4 = 6
- y_2, x_1: 2 + 4 = 6
- x_1, y_1: 2 + 4 = 6
- x_1, y_2: 2 + 4 = 6
これらの和は 34 です.
入力例 2
30 40 50
出力例 2
616365902
スコアの和を 10^9 + 7 で割った余りを出力することを忘れないでください.
Score : 900 points
Problem Statement
There is a rectangular sheet of paper with height H+1 and width W+1. We introduce an xy-coordinate system so that the four corners of the sheet are (0, 0), (W + 1, 0), (0, H + 1) and (W + 1, H + 1).
This sheet can be cut along the lines x = 1,2,...,W and the lines y = 1,2,...,H. Consider a sequence of operations of length K where we choose K of these H + W lines and cut the sheet along those lines one by one in some order.
Let the score of a cut be the number of pieces of paper that exist just after the cut. The score of a sequence of operations is the sum of the scores of all of the K cuts.
Find the sum of the scores of all possible sequences of operations of length K. Since this value can be extremely large, print the number modulo 10^9 + 7.
Constraints
- 1 \leq H,W \leq 10^7
- 1 \leq K \leq H + W
- H, W and K are integers.
Input
Input is given from Standard Input in the following format:
H W K
Output
Print the sum of the scores, modulo 10^9 + 7.
Sample Input 1
2 1 2
Sample Output 1
34
Let x_1, y_1 and y_2 denote the cuts along the lines x = 1, y = 1 and y = 2, respectively. The six possible sequences of operations and the score of each of them are as follows:
- y_1, y_2: 2 + 3 = 5
- y_2, y_1: 2 + 3 = 5
- y_1, x_1: 2 + 4 = 6
- y_2, x_1: 2 + 4 = 6
- x_1, y_1: 2 + 4 = 6
- x_1, y_2: 2 + 4 = 6
The sum of these is 34.
Sample Input 2
30 40 50
Sample Output 2
616365902
Be sure to print the sum modulo 10^9 + 7.