AtCoder Regular Contest 134

A - Bridge and Sheets

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

すぬけ君は長さ L の橋を買いました。すぬけ君は、この橋を長さ W のシートで覆うことにしました。

すぬけ君がシートを橋の左端から実数 x(0 \leq x \leq L-W) のところから設置すると、橋の左端から x 以上 x+W 以下の部分が覆われます(境界を含むことに注意してください)。

すぬけ君はすでに N 枚のシートを設置しています。 i 番目のシートは橋の左端から a_i のところから設置されています。

この橋全体を覆うには少なくとも何枚のシートが追加で必要でしょうか？橋全体が覆われているとは、0 以上 L 以下の任意の実数 x について、橋の左端から x の部分を覆うようなシートが存在していることをいいます。

制約

与えられる入力は全て整数
1 \leq N \leq 10^{5}
1 \leq W \leq L \leq 10^{18}
0 \leq a_1 < a_2 < \cdots < a_N \leq L-W

入力

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

N L W
a_1 \cdots a_N

出力

橋全体を覆うのに追加で必要なシートの枚数の最小値を出力せよ。

入力例 1

2 10 3
3 5

出力例 1

例えば、左端から 0、7 のところにシートを 1 枚ずつ設置すると橋全体を覆うことができます。

入力例 2

5 10 3
0 1 4 6 7

出力例 2

入力例 3

12 1000000000 5
18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

出力例 3

199999992

Score : 300 points

Problem Statement

Snuke bought a bridge of length L. He decided to cover this bridge with blue tarps of length W each.

Below, a position on the bridge is represented by the distance from the left end of the bridge. When a tarp is placed so that its left end is at the position x (0 \leq x \leq L-W, x is real), it covers the range [x, x+W]. (Note that both ends are included.)

He has already placed N tarps. The left end of the i-th tarp is at the position a_i.

At least how many more tarps are needed to cover the bridge entirely? Here, the bridge is said to be covered entirely when, for any real number x between 0 and L (inclusive), there is a tarp that covers the position x.

Constraints

All values in input are integers.
1 \leq N \leq 10^{5}
1 \leq W \leq L \leq 10^{18}
0 \leq a_1 < a_2 < \cdots < a_N \leq L-W

Input

Input is given from Standard Input in the following format:

N L W
a_1 \cdots a_N

Output

Print the minimum number of tarps needed to cover the bridge entirely.

Sample Input 1

2 10 3
3 5

Sample Output 1

The bridge will be covered entirely by, for example, placing two tarps so that their left ends are at the positions 0 and 7.

Sample Input 2

5 10 3
0 1 4 6 7

Sample Output 2

Sample Input 3

12 1000000000 5
18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

Sample Output 3

199999992

B - Reserve or Reverse

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の文字列 s が与えられます。 s の i 文字目は s_i と表します。

すぬけ君は以下の手順で s を変化させます。

(1,2, \ldots, N) の長さが偶数の（連続するとは限らない）部分列 x=(x_1, x_2, \ldots, x_{2k}) を選ぶ(k=0 でも構わない)。
s_{x_1} と s_{x_{2k}} を入れ替える。
s_{x_2} と s_{x_{2k-1}} を入れ替える。
s_{x_3} と s_{x_{2k-2}} を入れ替える。
\vdots
s_{x_{k}} と s_{x_{k+1}} を入れ替える。

すぬけ君が手順を終えたあとの s としてありうる文字列のうち、辞書順最小のものを求めてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

1 \leq N \leq 2 \times 10^5
s は長さ N の英小文字のみからなる文字列

入力

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

N
s

出力

すぬけ君が手順を終えたあとの s としてありうる文字列のうち、辞書順最小のものを出力せよ。

入力例 1

4
dcab

出力例 1

acdb

x=(1,3) のとき、s_{1} と s_{3} のみが入れ替わります。
手順を終えたあとの s は acdb となり辞書順最小です。

入力例 2

2
ab

出力例 2

ab

x=() のとき、手順を終えたあとの s は ab となり辞書順最小です。
x の長さが 0 でもよいことに注意してください。

入力例 3

16
cabaaabbbabcbaba

出力例 3

aaaaaaabbbbcbbbc

入力例 4

17
snwfpfwipeusiwkzo

出力例 4

effwpnwipsusiwkzo

Score : 400 points

Problem Statement

Given is a string s of length N. Let s_i denote the i-th character of s.

Snuke will transform s by the following procedure.

Choose an even length (not necessarily contiguous) subsequence x=(x_1, x_2, \ldots, x_{2k}) of (1,2, \ldots, N) (k may be 0).
Swap s_{x_1} and s_{x_{2k}}.
Swap s_{x_2} and s_{x_{2k-1}}.
Swap s_{x_3} and s_{x_{2k-2}}.
\vdots
Swap s_{x_{k}} and s_{x_{k+1}}.

Among the strings that s can become after the procedure, find the lexicographically smallest one.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

1 \leq N \leq 2 \times 10^5
s is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the lexicographically smallest possible string s after the procedure by Snuke.

Sample Input 1

4
dcab

Sample Output 1

acdb

When x=(1,3), the procedure just swaps s_{1} and s_{3}.
The s after the procedure is acdb, the lexicographically smallest possible result.

Sample Input 2

2
ab

Sample Output 2

ab

When x=(), the s after the procedure is ab, the lexicographically smallest possible result.
Note that x may have a length of 0.

Sample Input 3

16
cabaaabbbabcbaba

Sample Output 3

aaaaaaabbbbcbbbc

Sample Input 4

17
snwfpfwipeusiwkzo

Sample Output 4

effwpnwipsusiwkzo

C - The Majority

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 から K の番号がついた K 個の箱があります。はじめ、箱は全て空です。

すぬけ君は 1 以上 N 以下の整数が書かれたボールをいくつか持っています。すぬけ君が持っているボールのうち、i が書かれたものは a_i 個あります。同じ整数が書かれたボール同士は区別できません。

すぬけ君は持っている全てのボールを箱にしまうことにしました。すぬけ君はどの箱についても 1 と書かれたボールが過半数を占めるようにしたいです。過半数を占めるとは、1 と書かれたボールの個数がそれ以外のボールの個数より多いことを意味します。

そのようなしまい方の個数を 998244353 で割ったあまりを求めてください。

2 つのしまい方が異なるとは、1 \leq i \leq K, 1 \leq j \leq N を満たす整数の組 (i,j) であって、箱 i に入っている j が書かれたボールの個数が異なるようなものが存在することをいいます。

制約

与えられる入力は全て整数
1 \leq N \leq 10^5
1 \leq K \leq 200
1 \leq a_i < 998244353

入力

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

N K 
a_1 \cdots a_N

出力

どの箱も 1 と書かれたボールが過半数を占めるようなしまい方の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

2 2
3 1

出力例 1

1 と書かれたボールが過半数を占めるようなしまい方は 2 通りあります。
例えば 1 と書かれたボールを箱 1 に 2 個、箱 2 に 1 個入れ、2 と書かれたボールを箱 1 に 1 個入れたとき条件を満たします。

入力例 2

2 1
1 100

出力例 2

条件を満たすようなしまい方が存在しないこともあります。

入力例 3

20 100
1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

出力例 3

313918676

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

Score : 500 points

Problem Statement

There are K boxes numbered 1 to K. Initially, all boxes are empty.

Snuke has some balls with integers from 1 to N written on them. Among them, a_i balls have the number i. Balls with the same integer written on them cannot be distinguished.

Snuke has decided to put all of his balls in the boxes. He wants the balls with the number 1 to have a majority in every box. In other words, in every box, the number of balls with 1 should be greater than that of the other balls.

Find the number of such ways to put the balls in the boxes, modulo 998244353.

Two ways are distinguished when there is a pair of integers (i,j) satisfying 1 \leq i \leq K, 1 \leq j \leq N such that the numbers of balls with j in Box i are different.

Constraints

All values in input are integers.
1 \leq N \leq 10^5
1 \leq K \leq 200
1 \leq a_i < 998244353

Input

Input is given from Standard Input in the following format:

N K 
a_1 \cdots a_N

Output

Print the number of ways, modulo 998244353, to put the balls in the boxes so that the balls with the number 1 have a majority in every box.

Sample Input 1

2 2
3 1

Sample Output 1

There are two ways to put the balls so that the balls with the number 1 will be in the majority.
One way to do so is to put two of the balls with 1 in Box 1 and the other one in Box 2, and put the one ball with 2 in Box 1.

Sample Input 2

2 1
1 100

Sample Output 2

There may be no way to put the balls in the boxes to meet the requirement.

Sample Input 3

20 100
1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

Sample Output 3

313918676

Be sure to find the count modulo 998244353.

D - Concatenate Subsequences

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ 2N の数列 a が与えられます。

すぬけ君が (1,2, \ldots, N) の空でない（連続するとは限らない）部分列 x=(x_1,x_2,\ldots,x_k) を用いて、数列を作ろうとしています。作られる数列は、a の x_1 番目、x_2 番目、\ldots、x_k 番目、x_{1}+N 番目、\ldots、x_{k}+N 番目の要素を抜き出してこの順で連結した数列です。

すぬけ君が作ることができる数列のうち、辞書順最小のものを求めてください。

数列の辞書順とは？

相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します。

以下では S の i 番目の要素を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S と T のうち長さが短い方の数列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j が T_j より（数として）小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

与えられる入力は全て整数
1 \leq N \leq 10^5
1 \leq a_i \leq 10^9

入力

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

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

出力

すぬけ君が作ることができる数列のうち、辞書順最小のものを出力せよ。

入力例 1

3
2 1 3 1 2 2

出力例 1

1 2

x = (2) とします。
このとき、作られる数列は (1,2) となり辞書順最小です。

入力例 2

10
38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55

出力例 2

38 38 38 52 53 77 80 55

入力例 3

12
52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52

出力例 3

22 22 50 65 54 52

Score : 600 points

Problem Statement

Given is an integer sequence a of length 2N.

Snuke is going to make a sequence using a non-empty (not necessarily contiguous) subsequence x=(x_1,x_2,\ldots,x_k) of (1,2, \ldots, N). The sequence will be made by extracting and concatenating the x_1-th, x_2-th, \ldots, x_k-th, (x_{1}+N)-th, \ldots, (x_{k}+N)-th elements of a in this order.

Find the lexicographically smallest sequence that Snuke can make.

Lexicographical order on sequences

Here is the algorithm to determine the lexicographical order between different sequences S and T.

Below, let S_i denote the i-th element of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j is smaller than T_j in numerical order, we determine that S \lt T and quit; if S_j is greater than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

All values in input are integers.
1 \leq N \leq 10^5
1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

Print the lexicographically smallest sequence that Snuke can make.

Sample Input 1

3
2 1 3 1 2 2

Sample Output 1

1 2

We choose x = (2).
Then, the resulting sequence will be (1,2), the lexicographically smallest possible result.

Sample Input 2

10
38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55

Sample Output 2

38 38 38 52 53 77 80 55

Sample Input 3

12
52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52

Sample Output 3

22 22 50 65 54 52

E - Modulo Nim

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

すぬけ君は何も書かれていない黒板を見つけました。

すぬけ君が N 回黒板に操作をします。 i 回目の操作では黒板に 1 以上 a_i 以下の整数を選んで書き込みます。

黒板に N 個の整数が書き込まれたあと、先手太郎君と後手次郎君がこの黒板を使ったゲームで遊ぶ予定です。ゲームでは先手太郎君から始めて、交互に以下の操作を行います。

黒板に書かれている最大の整数を X とする。
- X=0 のとき、手番のプレイヤーの勝ちとしてゲームを終了する。
1 以上 X 以下の整数を選ぶ(これを m とする)。
黒板に書かれている N 個の整数をそれぞれ m で割ったあまりに置き換える。

すぬけ君の書き込み方は \prod_{i=1}^{N}a_i 通りありえますが、そのうち 2 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を 998244353 で割ったあまりを求めてください。

制約

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

入力

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

N
a_1 a_2 \cdots a_N

出力

2 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

1
3

出力例 1

先手太郎君が勝つのはすぬけ君が 3 を書き込んだ場合に限られます。
それ以外の場合、先手太郎君は黒板に書かれている整数が 0 になるように手を打つしかありません。

入力例 2

2
5 10

出力例 2

入力例 3

20
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200

出力例 3

273710435

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

Score : 900 points

Problem Statement

Snuke found a blackboard with nothing written on it.

He will do N operations on this blackboard. In the i-th operation, he chooses an integer between 1 and a_i (inclusive) and writes it on the blackboard.

After N integers are written on the blackboard, Taro The First and Jiro The Second will play a game using it. In the game, the two alternately do the operation below, with Taro The First going first.

Let X be the largest integer written on the blackboard.
- If X=0, the current player wins and the game ends.
Choose an integer m between 1 and X (inclusive).
Replace each of the N integers written on the blackboard with its remainder when divided by m.

There are \prod_{i=1}^{N}a_i ways for Snuke to write numbers on the blackboard. Find the number of ways among them that will result in Taro The First's win if both players play optimally, modulo 998244353.

Constraints

All values in input are integers.
1 \leq N \leq 200
1 \leq a_i \leq 200

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \cdots a_N

Output

Print the number of ways to write integers that will result in Taro The First's win if both players play optimally, modulo 998244353.

Sample Input 1

1
3

Sample Output 1

Taro The First will win only if Snuke writes 3.
Otherwise, Taro The First can only play a move that makes the integer on the blackboard 0.

Sample Input 2

2
5 10

Sample Output 2

Sample Input 3

20
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200

Sample Output 3

273710435

Be sure to find the count modulo 998244353.

F - Flipping Coins

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

1,2,\ldots,N の番号がついた N 枚のコインが並べられています。はじめ、全てのコインは表を向いています。

すぬけ君は (1,\ldots,N) を並び替えて得られる順列 p を等確率で 1 つ選び N 回操作を行います。 i 回目の操作では以下の処理が行われます。

i 番のコインが裏向きならば何もしない。
i 番のコインが表向きならば i 番のコインをひっくり返した後 p_i 番のコインをひっくり返す。

N 回の操作の後、表向きのコインの枚数を k としてすぬけ君はお母さんから W^k 円もらえます。

すぬけ君が得られるお金の期待値に N! をかけた値(これは整数になることが証明できます)を 998244353 で割ったあまりを求めてください。

制約

与えられる入力は全て整数
1 \leq N \leq 2 \times 10^5
1 \leq W < 998244353

入力

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

N W

出力

すぬけ君が得られるお金の期待値に N! をかけた値を 998244353 で割った余りを出力せよ。

入力例 1

4 2

出力例 1

p=(1,4,2,3) のとき、以下のように操作が行われます。
- 1 回目の操作では 1 番のコインが裏向きになり、その後 1 番のコインが表向きになります。
- 2 回目の操作では 2 番のコインが裏向きになり、その後 4 番のコインが裏向きになります。
- 3 回目の操作では 3 番のコインが裏向きになり、その後 2 番のコインが表向きになります。
- 4 回目の操作では何も行われません。
最終的に 2 枚のコインが表向きのため、4 円もらえます。

入力例 2

2 100

出力例 2

入力例 3

200000 12345

出力例 3

541410753

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

Score : 1000 points

Problem Statement

There are N coins numbered 1, 2, \ldots, N arranged in a row. Initially, all coins face up.

Snuke chooses a permutation p of (1,\ldots,N) with equal probability, and do N operations. The i-th operation does the following.

If the coin numbered i faces down, do nothing.
If the coin numbered i faces up, turn that coin over and then turn over the coin numbered p_i.

After the N operations, Snuke will receive W^k yen (Japanese currency) from his mother, where k is the number of coins facing up.

Find the expected value of the amount Snuke will get, multiplied by N! (it can be proved that this is an integer), modulo 998244353.

Constraints

All values in input are integers.
1 \leq N \leq 2 \times 10^5
1 \leq W < 998244353

Input

Input is given from Standard Input in the following format:

N W

Output

Print the expected value of the amount Snuke will get, multiplied by N!, modulo 998244353.

Sample Input 1

4 2

Sample Output 1

When p=(1,4,2,3), the operations go as follows.
- In the 1-st operation, the coin numbered 1 faces down, and then the coin numbered 1 faces up.
- In the 2-nd operation, the coin numbered 2 faces down, and then the coin numbered 4 faces down.
- In the 3-rd operation, the coin numbered 3 faces down, and then the coin numbered 2 faces up.
- In the 4-th operation, nothing is done.
In the end, two coins face up, so he receives 4 yen.

Sample Input 2

2 100

Sample Output 2

Sample Input 3

200000 12345

Sample Output 3

541410753

Be sure to find the value modulo 998244353.