KEYENCE Programming Contest 2021

A - Two Sequences 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

すぬけ君は長さ N の数列 a,b を持っています。 a,b の i 番目の数はそれぞれ a_i,b_i です。

すぬけ君は a,b を使って長さ N の数列 c を作ることにしました。 1 \leq n \leq N を満たす n について、c の n 番目の数 c_n は 1 \leq i \leq j \leq n を満たすような (i,j) について a_i b_j を計算したときの最大値です。より形式的には c_n は c_n = \max_{1 \leq i \leq j \leq n} a_{i}b_{j} で表される数です。

c_1, c_2, \ldots, c_{N} を求めてください。

制約

与えられる入力は全て整数
1 \leq N \leq 2 \times 10^{5}
1 \leq a_i, b_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_{1} a_{2} \cdots a_{N}
b_{1} b_{2} \cdots b_{N}

出力

N 行出力せよ。上から n 行目では c_{n} を出力せよ。

入力例 1

3
3 2 20
1 4 1

出力例 1

3
12
20

c_{1} = \max(a_{1}b_{1}) = 3 です。
c_{2} = \max(a_{1}b_{1}, a_{1}b_{2},a_{2}b_{2}) = 12 です。
c_{3} = \max(a_{1}b_{1}, a_{1}b_{2}, a_{1}b_{3}, a_{2}b_{2},a_{2}b_{3},a_{3}b_{3}) = 20 です。

入力例 2

20
715806713 926832846 890153850 433619693 890169631 501757984 778692206 816865414 50442173 522507343 546693304 851035714 299040991 474850872 133255173 905287070 763360978 327459319 193289538 140803416
974365976 488724815 821047998 371238977 256373343 218153590 546189624 322430037 131351929 768434809 253508808 935670831 251537597 834352123 337485668 272645651 61421502 439773410 621070911 578006919

出力例 2

697457706539596888
697457706539596888
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026

Score : 300 points

Problem Statement

Snuke has two number sequences a and b, each of length N. The i-th number of a is a_i, and that of b is b_i.

Using these sequences, he has decided to make a new sequence c of length N. For each n such that 1 \leq n \leq N, c_n, the n-th number of c, is the maximum value of a_i b_j for a pair (i,j) such that 1 \leq i \leq j \leq n. Formally, we have c_n = \max_{1 \leq i \leq j \leq n} a_{i}b_{j}.

Find c_1, c_2, \ldots, c_{N}.

Constraints

All values in input are integers.
1 \leq N \leq 2 \times 10^{5}
1 \leq a_i, b_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_{1} a_{2} \cdots a_{N}
b_{1} b_{2} \cdots b_{N}

Print

Print N lines. The n-th line from the top should contain c_{n}.

Sample Input 1

3
3 2 20
1 4 1

Sample Output 1

3
12
20

We have:

c_{1} = \max(a_{1}b_{1}) = 3;
c_{2} = \max(a_{1}b_{1}, a_{1}b_{2},a_{2}b_{2}) = 12;
c_{3} = \max(a_{1}b_{1}, a_{1}b_{2}, a_{1}b_{3}, a_{2}b_{2},a_{2}b_{3},a_{3}b_{3}) = 20.

Sample Input 2

20
715806713 926832846 890153850 433619693 890169631 501757984 778692206 816865414 50442173 522507343 546693304 851035714 299040991 474850872 133255173 905287070 763360978 327459319 193289538 140803416
974365976 488724815 821047998 371238977 256373343 218153590 546189624 322430037 131351929 768434809 253508808 935670831 251537597 834352123 337485668 272645651 61421502 439773410 621070911 578006919

Sample Output 2

697457706539596888
697457706539596888
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026

B - Mex Boxes

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

すぬけ君は一つの整数が書かれたボールを N 個持っています。ボールに書かれている数はそれぞれ a_1, a_2, \ldots, a_N です。

すぬけ君はこの N 個のボールを K 個の箱に割り振って入れることにしました。どのボールも箱に入れる必要はありますが、ボールが入っていない箱やボールが複数入っている箱があっても構いません。

すぬけ君がボールを入れ終わるとそれぞれの箱の蓋に整数が表示されます。表示される整数を x とすると、x は箱の中に x が書かれたボールが存在しないような最小の非負整数です。例えば、空の箱の蓋には 0 が、中に 0,1,3,5 と書かれたボールが入っている箱の蓋には 2 が、中に 1,2,3 と書かれたボールが入っている箱の蓋には 0 が表示されます。

箱の蓋に表示される整数の総和としてありうる値の最大値を求めてください。

制約

与えられる入力は全て整数
1 \leq K \leq N \leq 3 \times 10^{5}
0 \leq a_i < N

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 a_2 \cdots a_N

出力

箱の蓋に表示される整数の総和としてありうる値の最大値を出力せよ。

入力例 1

4 2
0 1 0 2

出力例 1

箱に入っているボールに書かれた数の集合が \{0,1,2 \},\{0\} となるように割り振って入れるのが最適です。
箱の蓋には 3,1 がそれぞれ表示され、これらの総和は 4 となります。

入力例 2

5 2
0 1 1 2 3

出力例 2

箱に入っているボールに書かれた数の(多重)集合が \{0,1,1,2,3\}, \{\} となるように割り振って入れるのが最適です。
箱の蓋には 4,0 がそれぞれ表示され、これらの総和は 4 となります。
ボールの入っていない箱があっても構わないことに注意してください。

入力例 3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

出力例 3

Score : 400 points

Problem Statement

Snuke has N balls, each with an integer written on it. The numbers on the balls are a_1, a_2, \ldots, a_N.

He has decided to put these N balls in K boxes. Every ball must be in some box, but there may be boxes with zero or multiple balls.

After he put the balls in the boxes, the lid of each box will show an integer. Let x be the integer shown on a box. x is the minimum non-negative integer such that the box contains no ball with x. For example, the lid of an empty box will show 0; the lid of a box with balls 0, 1, 3, 5 will show 2; the lid of a box with balls 1, 2, 3 will show 0.

Find the maximum possible sum of the integers the lids show.

Constraints

All values in input are integers.
1 \leq K \leq N \leq 3 \times 10^{5}
0 \leq a_i < N

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \cdots a_N

Output

Print the maximum possible sum of the integers the lids show.

Sample Input 1

4 2
0 1 0 2

Sample Output 1

An optimal solution is to allocate the sets of balls \{0,1,2 \},\{0\} to the boxes.
In this case, the lids show 3, 1, respectively, for a total of 4.

Sample Input 2

5 2
0 1 1 2 3

Sample Output 2

An optimal solution is to allocate the (multi)sets of balls \{0,1,1,2,3\}, \{\} to the boxes.
In this case, the lids show 4, 0, respectively, for a total of 4.
Note that we may have empty boxes.

Sample Input 3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

Sample Output 3

C - Robot on Grid

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

H 行 W 列のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と書くことにします。それぞれのマスには R, D, X のいずれかの文字を書き込むことができます。はじめ、どのマスにも文字は書き込まれていません。

すぬけ君は K 個のマスを選んで文字を書き込みました。 i 番目に文字を書き込んだマスは (h_i,w_i) で、書き込んだ文字は c_i でした。

残りのマスへの文字の書き込み方は 3^{HW-K} 通りあります。それぞれの場合について以下の問題の答えを計算し、その総和を 998244353 で割ったあまりを求めてください。

上記のマス目上を移動可能なロボットがあります。ロボットは (i,j) にいるとき、(i+1,j),(i,j+1) のいずれかに移動することができます。ただし、(i,j) に R と書かれていた場合は (i,j+1) にのみ、D と書かれていた場合は (i+1,j) にのみ移動することができます。X と書かれていた場合はどちらにも移動可能です。

ロボットを (1,1) に設置したとき、ロボットがマス目の外に出ずに (H,W) に到達するようなロボットの移動経路は何通りありますか？ただし、ロボットは (H,W) に到達した時点で停止するものとします。

ここで、2 つの移動経路が異なるとはロボットが通ったマスの集合が異なることをいいます。

制約

2 \leq H,W \leq 5000
0 \leq K \leq \min(HW,2 \times 10^5)
1 \leq h_i \leq H
1 \leq w_i \leq W
i \neq j ならば (h_i,w_i) \neq (h_j,w_j)
c_i は R, D, X のいずれか

入力

入力は以下の形式で標準入力から与えられる。

H W K
h_1 w_1 c_1
\vdots
h_K w_K c_K

出力

答えを出力せよ。

入力例 1

出力例 1

(1,2) のみまだ文字が書き込まれていません。
- R を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 1 通りです。
- D を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 2 通りです。
- X を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 2 通りです。
これらの総和である 5 を出力してください。

入力例 2

出力例 2

入力例 3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

出力例 3

139923295

998244353 で割ったあまりを求めるのを忘れずに。

Score : 500 points

Problem Statement

We have a grid with H rows and W columns of squares. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. On each square, we can write a letter: R, D, or X. Initially, every square is empty.

Snuke chose K of the squares and wrote characters on them. The i-th square he chose was (h_i,w_i), and he wrote the letter c_i on it.

There are 3^{HW-K} ways to write a letter on each of the remaining squares. Find the sum of the answers to the problem below for all those 3^{HW-K} ways, modulo 998244353.

We have a robot that can walk on the grid. When it is at (i,j), it can move to (i+1, j) or (i, j+1).
However, if R is written on (i, j), it can only move to (i, j+1); if D is written on (i, j), it can only move to (i+1, j). If X is written on (i, j), both choices are possible.

When the robot is put at (1, 1), how many paths can the robot take to reach (H, W) without going out of the grid? We assume the robot halts when reaching (H, W).

Here, we distinguish two paths when the sets of squares traversed by the robot are different.

Constraints

2 \leq H,W \leq 5000
0 \leq K \leq \min(HW,2 \times 10^5)
1 \leq h_i \leq H
1 \leq w_i \leq W
(h_i,w_i) \neq (h_j,w_j) for i \neq j.
c_i is R, D, or X.

Input

Input is given from Standard Input in the following format:

H W K
h_1 w_1 c_1
\vdots
h_K w_K c_K

Output

Print the answer.

Sample Input 1

Sample Output 1

Only (1,2) is empty.
- If we write R on it, there is one way that the robot can take to reach (H, W).
- If we write D on it, there are two ways that the robot can take to reach (H, W).
- If we write X on it, there are two ways that the robot can take to reach (H, W).
We should print the sum of these counts: 5.

Sample Input 2

Sample Output 2

Sample Input 3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

Sample Output 3

139923295

Be sure to compute the sum modulo 998244353.

D - Choosing Up Sides

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N を正の整数とします。 2 つの 2^{N-1} 人チームが対戦する競技があります。

1 から 2^N の番号がついた 2^N 人の人がいます。すぬけ監督は、彼らを A と B の 2 つの 2^{N-1} 人チームに分けて対戦させる、という操作を何回でも行うことができます。

すぬけ監督は、1 回以上操作を行った後、以下の 2 つの条件の両方を満たすようにしたいです。

ある整数 n が存在して、1 \leq i < j \leq 2^N を満たす任意の (i,j) について、人 i と人 j が同じチームだった回数が n 回
ある整数 m が存在して、1 \leq i < j \leq 2^N を満たす任意の (i,j) について、人 i と人 j が 異なる チームだった回数が m 回

すぬけ監督の要望を満たすような操作列が存在することが証明できます。そのうち 操作回数が最小 であるようなものの一例を示してください。

制約

与えられる入力は全て整数
1 \leq N \leq 8

入力

入力は以下の形式で標準入力から与えられる。

出力

下記のフォーマットで操作列を出力せよ。

K
s_1
s_2
\vdots
s_K

ここで、K は操作列の長さを、s_i は i 回目の操作でのチーム分けを表す。 s_{i} は長さ 2^N の A, B のみからなる文字列であり、s_{i} の {j} 文字目が A ならば i 回目の操作で人 j はチーム A に所属していたことを、B ならばチーム B に所属していたことを表す。A, B は s_i において 2^{N-1} 回ずつ出現する必要があることに注意せよ。

K が要望を満たす操作列の長さとして最小であり、操作の結果すぬけ監督の要望が満たされたならば正解となる。

入力例 1

出力例 1

1
AB

1 回操作を行うことですぬけ監督の要望を満たすことができます。
操作は 1 回以上行う必要があることに注意してください。

Score : 700 points

Problem Statement

Let N be a positive integer. Consider a competition where two teams, each with 2^{N-1} players, play against each other.

We have 2^N players numbered 1 through 2^N. Coach Snuke can do the following operation any number of times: separate the players into two teams A and B, each with 2^{N-1} players, and make them play against each other.

He wants to do this operation one or more times so that both of the following conditions are satisfied:

there exists an integer n such that, for every (i, j) such that 1 \leq i < j \leq 2^N, Player i and Player j have belonged to the same team exactly n times.
there exists an integer m such that, for every (i, j) such that 1 \leq i < j \leq 2^N, Player i and Player j have belonged to different teams exactly m times.

We can prove that there exist sequences of operations that achieve Snuke's objective. Among those sequences, present one sequence with the minimum possible number of operations.

Constraints

All values in input are integers.
1 \leq N \leq 8

Input

Input is given from Standard Input in the following format:

Output

Print a sequence of operations in the format below:

K
s_1
s_2
\vdots
s_K

Here, K represents the length of the sequence, and s_i represents the division into teams in the i-th operation. s_i should be a string of length 2^N consisting of A and B. In the i-th operation, if Player j belongs to Team A, the {j}-th character of s_{i} should be A; if Player j belongs to Team B, the {j}-th character of s_{i} should be B. Note that A and B each must occur exactly 2^{N-1} times in each s_i.

Your output will be accepted when K is the minimum possible length of a sequence of operations that achieves the objective, and the sequence actually achieves the objective.

Sample Input 1

Sample Output 1

1
AB

We can satisfy the objective with one operation.
Note that we must do at least one operation.

E - Greedy Ant

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

数直線上に N 個の飴があります。左から i 番目の飴は位置 2i にあり、美味しさ a_i の飴です。ここで、飴の美味しさは相異なることが保証されます。

すぬけ君と蟻が交互に飴を一つずつ取り合うことにしました。はじめに蟻が位置 1,3,\ldots, 2N+1 の一つを選んでそこに立ち、取り合いを開始します。

すぬけ君が先に飴を取ります。すぬけ君は、自分の手番において好きな飴を一つ選んで取ることができます。

蟻は、自分の手番において、自分がいる位置から左右それぞれの方向について最も近い位置にある飴のうち、美味しさが大きい方を選んで取ります。一方向にしか飴が存在しない場合は、その方向にある最も近い位置にある飴を取ります。

飴がなくなった時点で取り合いは終了します。蟻がはじめに立つ位置が 1, 3, \ldots, 2N+1 の場合のそれぞれについて、すぬけ君が取る飴の美味しさの総和としてありうる値の最大値を求めてください。

制約

与えられる入力は全て整数
1 \leq N \leq 400
1 \leq a_i \leq 10^{6}
a_i は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 \ldots a_N

出力

N+1 行出力せよ。i 行目では、蟻がはじめに位置 2i-1 に立ったときに、すぬけ君が取る飴の美味しさの総和としてありうる値の最大値を出力すること。

入力例 1

7
4 3 1 2 1000 2000 3000

出力例 1

蟻がはじめに位置 7 に立ったときのすぬけ君の最適な戦略の一例について説明します。
- すぬけ君は美味しさ 1 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は美味しさ 3 の飴です。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさが大きい方である美味しさ 3 の飴を取ります。
- すぬけ君は美味しさ 1000 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は美味しさ 4 の飴です。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさが大きい方である美味しさ 4 の飴を取ります。
- すぬけ君は美味しさ 2000 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は存在しません。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさ 2 の飴を取ります。
- すぬけ君は美味しさ 3000 の飴を取ります。
- すぬけ君の取った飴の美味しさの総和は 6001 です。これを超えるようなすぬけ君の飴の取り方は存在しません。

入力例 2

40
45651 92206 55173 24815 34809 73343 60978 57984 6919 89624 19693 30037 87070 6713 65976 37597 51929 93304 70911 7343 65414 38977 47998 52123 53590 35714 59319 50872 53850 40991 85668 8808 32846 70831 3416 42173 89538 73410 21502 69631

出力例 2

Score : 700 points

Problem Statement

There are N candies on a number line. The i-th candy from the left is at the position 2i and has the tastiness of a_i. Here, it is guaranteed that the tastinesses of all candies are distinct.

Snuke and Ant have decided to play a game of alternately taking one candy. At the beginning of the game, Ant chooses one of the positions 1,3,\ldots, 2N+1 and stands there.

Snuke goes first. In his turn, he can choose any one candy and get it.

In Ant's turn, she chooses the candy with the greater tastiness of the following two: the nearest candy to the left of her and the nearest candy to the right of her. If there are candies in only one direction, she chooses the nearest one.

The game ends when no candies are left. For each of the positions 1, 3, \ldots, 2N+1, find the maximum possible sum of the tastinesses of candies Snuke takes when Ant chooses that position.

Constraints

All values in input are integers.
1 \leq N \leq 400
1 \leq a_i \leq 10^{6}
a_i are distinct.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print N+1 lines. The i-th line should contain the maximum possible sum of the tastinesses of candies Snuke takes when Ant initially stands at the position 2i-1.

Sample Input 1

7
4 3 1 2 1000 2000 3000

Sample Output 1

We will explain one optimal strategy for Snuke when Ant initially stands at the position 7.
- Snuke chooses the candy of tastiness 1.
- The candies to the left and right of Ant have the tastinesses of 3 and 2, respectively. She chooses the one with the greater tastiness, that is, the one with tastiness 3.
- Snuke chooses the candy of tastiness 1000.
- The candies to the left and right of Ant have the tastinesses of 4 and 2, respectively. She chooses the one with the greater tastiness, that is, the one with tastiness 4.
- Snuke chooses the candy of tastiness 2000.
- There is no candy to the left of Ant, and the candy to the right of Ant has the tastiness of 2. She chooses this candy with tastiness 2.
- Snuke chooses the candy of tastiness 3000.
- The sum of the tastinesses of candies Snuke has taken is 6001. There is no way to take candies that results in a greater total tastiness.

Sample Input 2

40
45651 92206 55173 24815 34809 73343 60978 57984 6919 89624 19693 30037 87070 6713 65976 37597 51929 93304 70911 7343 65414 38977 47998 52123 53590 35714 59319 50872 53850 40991 85668 8808 32846 70831 3416 42173 89538 73410 21502 69631

Sample Output 2

F - Keyence Repetition

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

s を keyence を N 回繰り返した文字列とします。 s の 0 個以上の文字を削除した後、残った文字を元の順序を保ったまま連結して新しい文字列 s^{\prime} を作ることを考えます。

削除する位置の選び方は 2^{7N} 通りあります。これらのうち、s^{\prime} が t と一致するようなものの個数を 998244353 で割ったあまりを求めてください。

制約

1 \leq N \leq 10^{18}
1 \leq |t| \leq 2.5 \times 10^5
t は c, e, k, n, y のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N
t

出力

削除する位置の選び方のうち、s^{\prime} が t と一致するようなものの個数を 998244353 で割ったあまりを出力せよ。

入力例 1

2
key

出力例 1

s= keyencekeyence です。
s^{\prime}= key となるような削除する位置の選び方は 6 通りです。

入力例 2

2
ccc

出力例 2

s^{\prime}= ccc となるような削除する位置の選び方は 0 通りです。

入力例 3

100
keyneeneeeckyycccckkke

出力例 3

275429980

998244353 で割ったあまりを求めるのを忘れずに。

Score : 1000 points

Problem Statement

Let s be the concatenation of N copies of keyence. Consider deleting zero or more characters from s and concatenating the remaining characters without changing the order to make a new string s^{\prime}.

There are 2^{7N} ways to choose the positions at which we delete the characters. Among them, how many make s^{\prime} equal to t? Find the count modulo 998244353.

Constraints

1 \leq N \leq 10^{18}
1 \leq |t| \leq 2.5 \times 10^5
t is a string consisting of c, e, k, n, and y.

Input

Input is given from Standard Input in the following format:

N
t

Output

Print the number of ways to choose the positions at which we delete the characters so that s^{\prime} will be equal to t, modulo 998244353.

Sample Input 1

2
key

Sample Output 1

We have s= keyencekeyence.
There are six ways to choose the positions at which we delete the characters so that s^{\prime}= key.

Sample Input 2

2
ccc

Sample Output 2

There are zero ways to choose the positions at which we delete the characters so that s^{\prime}= ccc.

Sample Input 3

100
keyneeneeeckyycccckkke

Sample Output 3

275429980

Be sure to find the count modulo 998244353.