KEYENCE Programming Contest 2019

A - Beginning

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

B - KEYENCE String

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

連続した部分文字列 (空でも良い) を 1 度だけ取り除くことで keyence に変換することができる文字列をキーエンス型文字列と呼ぶことにします．

英小文字のみから成る文字列 S が与えられるので，S がキーエンス型文字列かどうか判定してください．

制約

S の長さは 7 以上 100 以下
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:

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

C - Exam and Wizard

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

(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

この場合は，何もしなくても全ての試験に合格できます．

入力例 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

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

(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

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

D - Double Landscape

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

(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 を出力します．

入力例 3

2 2
4 4
4 4

出力例 3

入力例 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

(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

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

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

E - Connecting Cities

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

例えば，都市 1 と都市 2 の間と，都市 1 と都市 3 の間に道路を建設することで，このコストを達成することができます．

入力例 2

3 1000
1 100 1

出力例 2

入力例 3

6 14
25 171 7 1 17 162

出力例 3

入力例 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

出力例 4

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

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

Sample Input 3

6 14
25 171 7 1 17 162

Sample Output 3

Sample Input 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

Sample Output 4

F - Paper Cutting

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

直線 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

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.