ACL Contest 1

A - Reachable Towns

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

2 次元平面上に N 個の街があります。i 個目の街の座標は (x_i, y_i) です。ここで、(x_1, x_2, \dots, x_N) と (y_1, y_2, \dots, y_N) は、ともに (1, 2, \dots, N) の順列となっています。

各 k = 1,2,\dots,N について、以下の問題の答えを求めてください。

rngさんが街 k にいる。 rngさんは、今いる街よりも「x, y 座標がともに小さい街」か「x, y 座標がともに大きい街」に移動することを好きな回数繰り返すことができる。 rngさんが到達可能な街は、(街 k を含めて) 何種類あるか？

制約

1 \leq N \leq 200,000
(x_1, x_2, \dots, x_N) は (1, 2, \dots, N) の並び替え
(y_1, y_2, \dots, y_N) は (1, 2, \dots, N) の並び替え
入力される数は全て整数である．

入力

N
x_1 y_1
x_2 y_2
:
x_N y_N

出力

N 行出力する。i 行目には、k = i のときの答えを出力すること。

入力例 1

出力例 1

街 3 からは街 4 に、また逆に街 4 からは街 3 へ移動できます。

入力例 2

出力例 2

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k. Rng can perform the following move arbitrarily many times:

move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

1 \leq N \leq 200,000
(x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).
(y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

Sample Output 1

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

Sample Output 2

B - Sum is Multiple

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

整数 N が与えられます．正の整数 k であって，(1+2+\cdots+k) が N の倍数になるもののうち，最小のものを求めてください．なお，このような正の整数 k が必ず存在することは証明できます．

制約

1 \leq N \leq 10^{15}
入力は全て整数である．

入力

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

出力

答えを一行に出力せよ．

入力例 1

出力例 1

1+2+\cdots+10=55 であり，これは確かに N=11 の倍数です． k \leq 9 で条件を満たすものは存在しないため，k=10 が答えになります．

入力例 2

20200920

出力例 2

Score : 600 points

Problem Statement

Given is an integer N. Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N. It can be proved that such a positive integer k always exists.

Constraints

1 \leq N \leq 10^{15}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print the answer in a line.

Sample Input 1

Sample Output 1

1+2+\cdots+10=55 holds and 55 is indeed a multple of N=11. There are no positive integers k \leq 9 that satisfy the condition, so the answer is k = 10.

Sample Input 2

20200920

Sample Output 2

C - Moving Pieces

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 行 M 列からなる盤面があります．この盤面の情報は N 個の文字列 S_1,S_2,\ldots,S_N によって表されます．具体的には，上から i 行目，左から j 列目のマスの状態は，以下のように表されます．

S_{i,j}=. : このマスは空である．
S_{i,j}=# : このマスには障害物が置かれている．
S_{i,j}=o : このマスには 1 つの駒が置かれている．

yosupo くんが，これから以下の操作を繰り返します．

駒を 1 つ選び，1 個下，もしくは 1 個右のマスに移動させる．ただし，他の駒もしくは障害物のあるマスに駒を移動させる操作は禁止されている．もちろん，駒が盤面を飛び出すような操作も行えない．

yosupo くんは，できるだけ多くの回数操作をしたいです．操作回数の最大値を求めてください．

制約

1 \leq N \leq 50
1 \leq M \leq 50
S_i は，.,#,o からなる長さ M の文字列．
1 \leq ( 駒の個数 )\leq 100．つまり，S_{i,j}=o を満たす (i,j) の個数は 1 個以上 100 個以下．

入力

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

N M
S_1
S_2
\vdots
S_N

出力

操作回数の最大値を一行に出力せよ．

入力例 1

3 3
o..
...
o.#

出力例 1

以下のように 4 回の操作を行えます．

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#

入力例 2

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

出力例 2

Score : 600 points

Problem Statement

There is a board with N rows and M columns. The information of this board is represented by N strings S_1,S_2,\ldots,S_N. Specifically, the state of the square at the i-th row from the top and the j-th column from the left is represented as follows:

S_{i,j}=. : the square is empty.
S_{i,j}=# : an obstacle is placed on the square.
S_{i,j}=o : a piece is placed on the square.

Yosupo repeats the following operation:

Choose a piece and move it to its right adjecent square or its down adjacent square. Moving a piece to squares with another piece or an obstacle is prohibited. Moving a piece out of the board is also prohibited.

Yosupo wants to perform the operation as many times as possible. Find the maximum possible number of operations.

Constraints

1 \leq N \leq 50
1 \leq M \leq 50
S_i is a string of length M consisting of ., # and o.
1 \leq ( the number of pieces )\leq 100. In other words, the number of pairs (i, j) that satisfy S_{i,j}=o is between 1 and 100, both inclusive.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the maximum possible number of operations in a line.

Sample Input 1

3 3
o..
...
o.#

Sample Output 1

Yosupo can perform operations 4 times as follows:

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#

Sample Input 2

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

Sample Output 2

D - Keep Distances

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

数直線上に N 個の点があり，そのうち i 番目の点は座標 X_i にあります．これらの点は座標の昇順に番号がついています．つまり，すべての i (1 \leq i \leq N-1) について，X_i<X_{i+1} が成り立ちます. また，整数 K が与えられます．

Q 個のクエリを処理してください．

i 番目のクエリでは，整数 L_i,R_i が与えられます．ここで，点の集合 s がよい集合であるとは，以下の条件をすべて満たすことを意味します．よい集合の定義がクエリごとに変わることに注意してください．

s に含まれる点は，X_{L_i},X_{L_i+1},\ldots,X_{R_i} のいずれかである．
s に含まれるどの異なる 2 点についても，その間の距離が K 以上である．
s のサイズは，上記の条件を満たす集合の中で最大である．

各クエリごとに，すべてのよい集合の和集合のサイズを求めてください．

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^9
0 \leq X_1 <X_2 < \cdots < X_N \leq 10^9
1 \leq Q \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq N
入力は全て整数である．

入力

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

N K
X_1 X_2 \cdots X_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

各クエリごとに，すべてのよい集合の和集合のサイズを一行に出力せよ．

入力例 1

出力例 1

4
2

1 つめのクエリでは，最大 3 つの点を集合に含めることができます．よい集合は，\{1,4,7\} と \{1,4,8\} の 2 つです．よって，すべてのよい集合の和集合のサイズは |\{1,4,7,8\}|=4 です．

2 つめのクエリでは，最大 1 つの点を集合に含めることができます．よい集合は，\{1\} と \{2\} の 2 つです．よって，すべてのよい集合の和集合のサイズは |\{1,2\}|=2 です．

入力例 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

出力例 2

Score : 800 points

Problem Statement

There are N points on a number line, i-th of which is placed on coordinate X_i. These points are numbered in the increasing order of coordinates. In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds. In addition to that, an integer K is given.

Process Q queries.

In the i-th query, two integers L_i and R_i are given. Here, a set s of points is said to be a good set if it satisfies all of the following conditions. Note that the definition of good sets varies over queries.

Each point in s is one of X_{L_i},X_{L_i+1},\ldots,X_{R_i}.
For any two distinct points in s, the distance between them is greater than or equal to K.
The size of s is maximum among all sets that satisfy the aforementioned conditions.

For each query, find the size of the union of all good sets.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^9
0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
1 \leq Q \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
X_1 X_2 \cdots X_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

For each query, print the size of the union of all good sets in a line.

Sample Input 1

Sample Output 1

4
2

In the first query, you can have at most 3 points in a good set. There exist two good sets: \{1,4,7\} and \{1,4,8\}. Therefore, the size of the union of all good sets is |\{1,4,7,8\}|=4.

In the second query, you can have at most 1 point in a good set. There exist two good sets: \{1\} and \{2\}. Therefore, the size of the union of all good sets is |\{1,2\}|=2.

Sample Input 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

Sample Output 2

E - Shuffle Window

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

(1, 2, ..., N) の順列 p_1, p_2, \dots, p_N と整数 K が与えられます。 maroonくんは i = 1, 2, \dots, N - K + 1 について、次の操作を順番に行います。

p_i, p_{i + 1}, \dots, p_{i + K - 1} を一様ランダムにシャッフルする。

すべての操作の後の数列の転倒数の期待値を求め、\bmod 998244353 で出力してください。

より正確には、期待値が有理数、つまりある既約分数 \frac{P}{Q} で表せること、更に R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まることがこの問題の制約より証明できます。よって、この R を出力してください。

また、数列 a_1, a_2, \dots, a_N の転倒数とは、i < j, a_i > a_j を満たす順序対 (i, j) の個数とします。

制約

2 \leq N \leq 200,000
2 \leq K \leq N
(p_1, p_2, \dots, p_N) は (1, 2, \dots, N) の並び替え
入力される数は全て整数である．

入力

N K
p_1 p_2 ... p_N

出力

期待値を \bmod 998244353 で出力せよ。

入力例 1

3 2
1 2 3

出力例 1

(1, 2, 3), (2, 1, 3), (1, 3, 2), (2, 3, 1) が、それぞれ \frac{1}{4} の確率で最終的な数列になります。これらの転倒数は 0, 1, 1, 2 なので、期待値は 1 です。

入力例 2

10 3
1 8 4 9 2 3 7 10 5 6

出力例 2

164091855

Score : 900 points

Problem Statement

Given are a permutation p_1, p_2, \dots, p_N of (1, 2, ..., N) and an integer K. Maroon performs the following operation for i = 1, 2, \dots, N - K + 1 in this order:

Shuffle p_i, p_{i + 1}, \dots, p_{i + K - 1} uniformly randomly.

Find the expected value of the inversion number of the sequence after all the operations are performed, and print it modulo 998244353.

More specifically, from the constraints of this problem, it can be proved that the expected value is always a rational number, which can be represented as an irreducible fraction \frac{P}{Q}, and that the integer R that satisfies R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Print this R.

Here, the inversion number of a sequence a_1, a_2, \dots, a_N is defined to be the number of ordered pairs (i, j) that satisfy i < j, a_i > a_j.

Constraints

2 \leq N \leq 200,000
2 \leq K \leq N
(p_1, p_2, \dots, p_N) is a permutation of (1, 2, \dots, N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 p_2 ... p_N

Output

Print the expected value modulo 998244353.

Sample Input 1

3 2
1 2 3

Sample Output 1

The final sequence is one of (1, 2, 3), (2, 1, 3), (1, 3, 2), (2, 3, 1), each with probability \frac{1}{4}. Their inversion numbers are 0, 1, 1, 2 respectively, so the expected value is 1.

Sample Input 2

10 3
1 8 4 9 2 3 7 10 5 6

Sample Output 2

164091855

F - Center Rearranging

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

長さ 3N の数列 A, B が与えられます。この 2 つの数列は、共に 1, 2, \dots, N をちょうど 3 個ずつ含みます。言い換えると、(1, 1, 1, 2, 2, 2, \dots, N, N, N) の並び替えになっています。

高橋くんは、数列 A に以下の操作を好きな回数繰り返し行えます。

1, 2, \dots, N から値を一つ選び、x とする。A は x をちょうど 3 つ含むが、このうち中央の要素を削除する。その後、A の先頭か末尾に x を追加する。

A を B に変更できるか判定してください。可能な場合は、変更に必要な最小の操作回数も求めてください。

制約

1 \leq N \leq 33
A, B は共に (1, 1, 1, 2, 2, 2, \dots, N, N, N) の並び替え。
入力される数は全て整数である。

入力

N
A_1 A_2 ... A_{3N}
B_1 B_2 ... B_{3N}

出力

変更可能な場合は最小の操作回数、不可能な場合は -1 を出力してください。

入力例 1

3
2 3 1 1 3 2 2 1 3
1 2 2 3 1 2 3 1 3

出力例 1

例えば以下のように操作するとよいです。

2 3 1 1 3 2 2 1 3 (スタート)
2 2 3 1 1 3 2 1 3 (x = 2 を選び、先頭に追加)
2 2 3 1 3 2 1 3 1 (x = 1 を選び、末尾に追加)
1 2 2 3 1 3 2 3 1 (x = 1 を選び、先頭に追加)
1 2 2 3 1 2 3 1 3 (x = 3 を選び、末尾に追加)

入力例 2

3
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3

出力例 2

入力例 3

3
2 3 3 1 1 1 2 2 3
3 2 2 1 1 1 3 3 2

出力例 3

-1

入力例 4

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

出力例 4

Score : 1800 points

Problem Statement

Given are integer sequences A and B of length 3N. Each of these two sequences contains three copies of each of 1, 2, \dots, N. In other words, A and B are both arrangements of (1, 1, 1, 2, 2, 2, \dots, N, N, N).

Tak can perform the following operation to the sequence A arbitrarily many times:

Pick a value from 1, 2, \dots, N and call it x. A contains exactly three copies of x. Remove the middle element of these three. After that, append x to the beginning or the end of A.

Check if he can turn A into B. If he can, print the minimum required number of operations to achieve that.

Constraints

1 \leq N \leq 33
A and B are both arrangements of (1, 1, 1, 2, 2, 2, \dots, N, N, N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_{3N}
B_1 B_2 ... B_{3N}

Output

If Tak can turn A into B, print the minimum required number of operations to achieve that. Otherwise, print -1.

Sample Input 1

3
2 3 1 1 3 2 2 1 3
1 2 2 3 1 2 3 1 3

Sample Output 1

For example, Tak can perform operations as follows:

2 3 1 1 3 2 2 1 3 (The initial state)
2 2 3 1 1 3 2 1 3 (Pick x = 2 and append it to the beginning)
2 2 3 1 3 2 1 3 1 (Pick x = 1 and append it to the end)
1 2 2 3 1 3 2 3 1 (Pick x = 1 and append it to the beginning)
1 2 2 3 1 2 3 1 3 (Pick x = 3 and append it to the end)

Sample Input 2

3
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3

Sample Output 2

Sample Input 3

3
2 3 3 1 1 1 2 2 3
3 2 2 1 1 1 3 3 2

Sample Output 3

-1

Sample Input 4

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