World Tour Finals 2024

A - Moving Slimes

Time Limit: 2 sec / Memory Limit: 2048 MiB

配点 : 700 点

問題文

数直線上に N 匹のスライムがおり，i 番目のスライムは座標 A_i にいます．これらの座標はすべて異なります．各スライムの重さは 1 です．また整数 K が与えられます．

あなたはまず K 匹のスライムを選び，選ばなかったスライムを数直線上から取り除きます．その後，選ばれたスライムは時刻 0 から以下のように移動を行います．

各スライムの移動: 自分より大きい座標にいるスライムの重さの総和を R，自分より小さい座標にいるスライムの重さの総和を L とする．そして，速度 R-L で移動する．ここで，速度が符号付きであることに注意せよ．つまり，R-L<0 のときスライムは数直線上を負の方向へ動くものとする．

2 匹以上のスライムが同時に同じ座標に到達したとき，それらのスライムは合体します．合体後のスライムの重さは合体前のスライムの重さの総和です．また合体後のスライムは上と同じ規則にしたがって移動します．

K 匹のスライムは合体を繰り返し，いずれ 1 匹のスライムになります．このスライムが誕生する瞬間を時刻 t とします．あなたの目標は，K 匹のスライムを上手に選び，この t を最大化することです． t の最大値を求めてください．

制約

2 \leq K \leq N \leq 250000
0 = A_1 < A_2 < \cdots < A_N \leq 10^9
入力される値はすべて整数

入力

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

N K
A_1 A_2 \cdots A_N

出力

答えを実数として出力せよ．絶対誤差または相対誤差が 10^{-9} 以下ならば，正解と判定される．

入力例 1

3 2
0 1 2

出力例 1

1.00000000000000000000

1 番目と 2 番目のスライムを選ぶと t=0.5 になります．
1 番目と 3 番目のスライムを選ぶと t=1 になります．
2 番目と 3 番目のスライムを選ぶと t=0.5 になります．

よって答えは 1 です．

入力例 2

4 3
0 1 4 9

出力例 2

2.83333333333333333333

1,2,4 番目のスライムを選んだ場合，スライムの移動の様子は以下のとおりです．

1,2,4 番目のスライムを便宜的に X,Y,Z と呼ぶことにする．
時刻 0 : X,Y,Z はそれぞれ速度 +2,0,-2 で移動を開始する．
時刻 1/2 : X と Y が座標 1 で合体する．合体後のスライムを XY と呼ぶことにする．XY は速度 1 で移動を開始する．Z はこのとき座標 8 におり，速度は -2 のままである．
時刻 17/6 : XY と Z が座標 10/3 で合体する．よって t=17/6 となる．

t を 17/6 より大きくすることはできないので，これが答えになります．

入力例 3

4 4
0 1 2 3

出力例 3

0.50000000000000000000

入力例 4

20 6
0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743

出力例 4

135453315.33333333333333333333

Score : 700 points

Problem Statement

There are N slimes on a number line, and the i-th slime is at coordinate A_i. All these coordinates are distinct. Each slime has a weight of 1. Also, you are given an integer K.

First, you will choose K slimes and remove the others from the number line. Then, from time 0, the chosen slimes will move as follows:

Movement of each slime: Let R be the total weight of slimes at coordinates greater than its own, and L be the total weight of slimes at coordinates less than its own. Then, it moves with a velocity of R-L. Note that the velocity can be negative. That is, it moves in the negative direction if R-L<0.

When two or more slimes reach the same coordinate at the same time, they merge. The weight of the merged slime is the sum of the weights of the slimes before merging. The merged slime will move according to the same rules as above.

The K slimes will continue to merge until there is only one slime left. Let t be the moment when this single slime is born. Your goal is to choose the K slimes so that t is maximized. Find the maximum value of t.

Constraints

2 \leq K \leq N \leq 250000
0 = A_1 < A_2 < \cdots < A_N \leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the answer as a real number. It will be considered correct if the absolute or relative error is at most 10^{-9}.

Sample Input 1

3 2
0 1 2

Sample Output 1

1.00000000000000000000

Choosing the 1st and 2nd slimes results in t=0.5.
Choosing the 1st and 3rd slimes results in t=1.
Choosing the 2nd and 3rd slimes results in t=0.5.

Thus, the answer is 1.

Sample Input 2

4 3
0 1 4 9

Sample Output 2

2.83333333333333333333

If you choose the 1st, 2nd, and 4th slimes, the slimes move as follows:

For convenience, call the 1st, 2nd, and 4th slimes X, Y, and Z, respectively.
At time 0: X, Y, and Z start moving with velocity +2, 0, and -2, respectively.
At time 1/2: X and Y merge at coordinate 1. The merged slime, called XY, starts moving with velocity 1. On the other hand, Z is at coordinate 8 and continues moving with velocity -2.
At time 17/6: XY and Z merge at coordinate 10/3. Thus, t=17/6.

It is impossible to make t larger than 17/6, so this is the answer.

Sample Input 3

4 4
0 1 2 3

Sample Output 3

0.50000000000000000000

Sample Input 4

20 6
0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743

Sample Output 4

135453315.33333333333333333333

B - 01 Inversion Expected

Time Limit: 2 sec / Memory Limit: 2048 MiB

配点 : 1000 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます．整数の組 (i,j) (1 \leq i < j \leq N) であって，S の i 文字目が 1, j 文字目が 0 であるようなものを転倒ペアと呼ぶことにします．

S 内に転倒ペアが存在する限り，以下の操作を行います．

転倒ペア (i,j) をランダムに一つ選ぶ．選択はこれ以前の選択と独立で，かつ一様ランダムであるとする．そして，S の i 文字目と j 文字目を入れ替える．

操作回数の期待値を \text{mod }{998244353} で求めてください．

期待値 \text{mod }{998244353} の定義

求める期待値は必ず有理数になることが証明できます．また，この問題の制約のもとでは，その値を既約分数 \frac{P}{Q} で表した時，Q \neq 0 \pmod{998244353} となることも証明できます．よって，R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります．この R を答えてください．

制約

1 \leq N \leq 250000
S は 0, 1 からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ．

入力例 1

2
10

出力例 1

操作回数の期待値は 1 です．

入力例 2

3
110

出力例 2

499122178

操作回数の期待値は 3/2 です．

入力例 3

1
0

出力例 3

入力例 4

10
1011000010

出力例 4

133099253

入力例 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

出力例 5

407907276

Score : 1000 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. We define an inversion pair as a pair of integers (i, j) (1 \leq i < j \leq N) such that the i-th character of S is 1 and the j-th character of S is 0.

As long as there is an inversion pair in S, perform the following operation:

Randomly choose an inversion pair (i, j). The choice is independent of previous choices and is uniformly random. Then, swap the i-th and j-th characters of S.

Find the expected number of operations, modulo 998244353.

What is the expected value modulo 998244353?

It can be proved that the sought expected value is always rational. Moreover, under the constraints of this problem, it can be proved that if the expected value is expressed as an irreducible fraction \frac{P}{Q}, then Q \neq 0 \pmod{998244353}. Thus, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

1 \leq N \leq 250000
S is a string of length N consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

2
10

Sample Output 1

The expected number of operations is 1.

Sample Input 2

3
110

Sample Output 2

499122178

The expected number of operations is 3/2.

Sample Input 3

1
0

Sample Output 3

Sample Input 4

10
1011000010

Sample Output 4

133099253

Sample Input 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111

Sample Output 5

407907276

C - Fuel

Time Limit: 2 sec / Memory Limit: 2048 MiB

配点 : 1500 点

問題文

以下の問題を T 個のテストケースについて解いてください．

今あなたは数直線上の座標 0 の位置におり，これから座標 L まで移動したいです．

移動には車を使用します．この車はタイプ 1 とタイプ 2 の 2 種類の燃料で動きます．各タイプについて，そのタイプの燃料タンクの容量は C リットルです．現在，両タイプの燃料タンクは満タンです．車は，いずれかのタイプの燃料を x リットル (x は燃料の残量を超えない任意の正整数) 消費することで，数直線上を好きな方向に距離 x だけ移動できます．どちらのタイプの燃料を使用するかは，移動の度にあなたが選ぶことができます．

数直線上には N 個の燃料ステーションがあります． i 番目の燃料ステーションは座標 X_i にあります．車がちょうど座標 X_i に存在するとき，タイプ K_i の燃料を 1 リットルあたりコスト 1 で買えます．もちろん，タンクの容量を超えて燃料を買うことはできません．

座標 L に到達することが可能かどうか判定し，可能ならば燃料の購入にかかるコストの総和の最小値を求めてください．

制約

1 \leq T \leq 250000
1 \leq N \leq 5000
1 \leq L \leq 10^9
1 \leq C \leq 10^9
0 < X_1 < X_2 < \cdots < X_N < L
K_i=1 or 2
1 個の入力に含まれるテストケースについて，N^2 の総和は 5000^2 を超えない
入力される値はすべて整数

入力

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

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N L C
X_1 X_2 \cdots X_N
K_1 K_2 \cdots K_N

出力

T 行出力せよ． i 行目には，i 番目のテストケースについて，座標 L へ到達することが不可能なら -1 を出力し，可能ならコストの総和の最小値を出力せよ．

入力例 1

5
1 10 4
7
1
1 10 6
7
1
2 12 3
5 7
1 1
2 12 3
5 7
1 2
20 749013197 23809523
46981984 70791437 118235723 132421762 180040807 203849360 251468335 275277857 322889975 346699150 394318091 418113855 465732891 489532137 537144103 558852533 606466719 630275002 677584754 701394209
1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2

出力例 1

2
0
-1
6
585545066743659

1 つめのテストケースについて説明します．以下の方法でコスト 2 で座標 L へ移動できます．

タイプ 1 の燃料を 3 リットル消費し，座標 0 \to 3 と移動する．タイプ 1 の燃料の残量は 1 リットルになる．
タイプ 2 の燃料を 4 リットル消費し，座標 3 \to 7 と移動する．タイプ 2 の燃料の残量は 0 リットルになる．
燃料ステーションでタイプ 1 の燃料を 2 リットル買う．タイプ 1 の燃料の残量は 3 リットルになる．
タイプ 1 の燃料を 3 リットル消費し，座標 7 \to 10 と移動する．タイプ 1 の燃料の残量は 0 リットルになる．

2 未満のコストで座標 L へ移動することはできません．よって答えは 2 です．

Score : 1500 points

Problem Statement

Solve the following problem for T test cases.

You are currently at coordinate 0 on a number line, and you want to reach coordinate L.

You will use a car for the movement. This car runs on two types of fuel: types 1 and 2. For each type, the car has a fuel tank of that type with a capacity of C liters. Currently, both fuel tanks are full. The car can consume x liters of either type of fuel (where x is any positive integer not exceeding the remaining fuel) to move x units in any direction on the number line. You can choose which type of fuel to use for each movement.

There are N fuel stations on the number line. The i-th fuel station is located at coordinate X_i. When the car is exactly at coordinate X_i, you can buy type-K_i fuel at a cost of 1 per liter. Of course, you cannot buy more fuel than allowed by the tank capacity.

Determine whether it is possible to reach coordinate L. If it is possible, find the minimum total cost of purchasing fuel.

Constraints

1 \leq T \leq 250000
1 \leq N \leq 5000
1 \leq L \leq 10^9
1 \leq C \leq 10^9
0 < X_1 < X_2 < \cdots < X_N < L
K_i=1 or 2
The sum of N^2 across all test cases in a single input does not exceed 5000^2.
All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N L C
X_1 X_2 \cdots X_N
K_1 K_2 \cdots K_N

Output

Print T lines. In the i-th line, for the i-th test case, print -1 if it is impossible to reach coordinate L, and print the minimum total cost of purchasing fuel otherwise.

Sample Input 1

5
1 10 4
7
1
1 10 6
7
1
2 12 3
5 7
1 1
2 12 3
5 7
1 2
20 749013197 23809523
46981984 70791437 118235723 132421762 180040807 203849360 251468335 275277857 322889975 346699150 394318091 418113855 465732891 489532137 537144103 558852533 606466719 630275002 677584754 701394209
1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2

Sample Output 1

2
0
-1
6
585545066743659

Let us explain the first test case. You can reach coordinate L with a cost of 2 as follows:

Consume 3 liters of type-1 fuel to move from coordinate 0 to 3. The remaining type-1 fuel is 1 liter.
Consume 4 liters of type-2 fuel to move from coordinate 3 to 7. The remaining type-2 fuel is 0 liters.
Buy 2 liters of type-1 fuel at the fuel station. The remaining type-1 fuel is 3 liters.
Consume 3 liters of type-1 fuel to move from coordinate 7 to 10. The remaining type-1 fuel is 0 liters.

It is impossible to reach coordinate L with a cost less than 2. Thus, the answer is 2.

D - Almost Bubble Sort

Time Limit: 10 sec / Memory Limit: 2048 MiB

配点 : 2000 点

問題文

(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます．

隣接要素の swap を 0 回以上行って，P が以下の条件を満たすようにしたいです．

P_i > P_{i+1} を満たす i の個数は高々 1 つである．

必要な swap の最小回数を求めてください．

制約

2 \leq N \leq 800000
(P_1,P_2,\cdots,P_N) は (1,2,\cdots,N) の順列
入力される値はすべて整数

入力

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

N
P_1 P_2 \cdots P_N

出力

答えを出力せよ．

入力例 1

3
3 2 1

出力例 1

P_1 と P_2 を swap することで P=(2,3,1) になり，P は条件を満たします．

入力例 2

4
2 4 1 3

出力例 2

入力例 3

6
2 3 1 6 4 5

出力例 3

入力例 4

20
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

出力例 4

Score : 2000 points

Problem Statement

You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

You want to perform zero or more swaps of adjacent elements so that P satisfies the following condition:

The number of indices i such that P_i > P_{i+1} is at most 1.

Find the minimum number of swaps required.

Constraints

2 \leq N \leq 800000
(P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N

Output

Print the answer.

Sample Input 1

3
3 2 1

Sample Output 1

Swapping P_1 and P_2 turns P into (2,3,1), which satisfies the condition.

Sample Input 2

4
2 4 1 3

Sample Output 2

Sample Input 3

6
2 3 1 6 4 5

Sample Output 3

Sample Input 4

20
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

Sample Output 4

E - Colorful Stamps

Time Limit: 4 sec / Memory Limit: 2048 MiB

配点 : 2000 点

問題文

以下の問題を T 個のテストケースについて解いてください．

N 行 N 列からなる盤面があります．上から i 行目，左から j 列目にあるマスをマス (i,j) と表すことにします．最初，すべてのマスは無色です．

あなたは N^2 個のスタンプを持っています．各整数組 (h,w) (1 \leq h,w \leq N) に対し，サイズ h \times w のスタンプが 1 つあり，これをスタンプ (h,w) と呼ぶことにします．すべてのスタンプの色は異なります．

「スタンプ (h,w) を押す」とは以下の操作を意味します．

スタンプを押す位置 (a,b) (1 \leq a \leq N-h+1,\ 1 \leq b \leq N-w+1) を選ぶ．そして，すべてのマス (i,j) (a \leq i \leq a+h-1, b \leq j \leq b+w-1) をスタンプ (h,w) の色で塗る．塗ろうとしたマスがすでに別の色で塗られている場合，色は上書きされる．

あなたの目標は，各スタンプをちょうど 1 回ずつ押して，最終的な盤面においてすべてのマスの色が異なるようにすることです．

あなたはすでに K 個のスタンプを押しました． i 番目に押したのはスタンプ (H_i,W_i) で，その位置は (A_i,B_i) でした．

目標を達成するように残り N^2-K 個のスタンプを押す方法を 1 つ示してください．なお，この問題では残りのスタンプを適切な順番で適切な位置に押すことで目標を達成できる入力のみが与えられます．

制約

1 \leq T
2 \leq N \leq 400
0 \leq K < N^2
1 \leq H_i,W_i \leq N
1 \leq A_i \leq N-H_i+1
1 \leq B_i \leq N-W_i+1
(H_i,W_i) \neq (H_j,W_j) (i \neq j)
1 個の入力に含まれるテストケースについて，N^2 の総和は 400^2 を超えない
残りのスタンプを適切な順番で適切な位置に押すことで目標を達成できるような入力のみが与えられる
入力される値はすべて整数

入力

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

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N K
H_1 W_1 A_1 B_1
H_2 W_2 A_2 B_2
\vdots
H_K W_K A_K B_K

出力

各テストケースについて以下の形式で答えを出力せよ．

h_1 w_1 a_1 b_1
h_2 w_2 a_2 b_2
\vdots
h_{N^2-K} w_{N^2-K} a_{N^2-K} b_{N^2-K}

これは，（すでに押した K 個のスタンプを除いて）i 番目に押すスタンプが (h_i,w_i) で，その位置が (a_i,b_i) であることを意味する．

入力例 1

出力例 1

1 つめのテストケースについて考えます．

（すでに押した K 個のスタンプを含めて）i 番目に押したスタンプの色を i で表すことにすると，盤面は以下のように変化します．

..     ->      11     ->      11     ->      31     ->      31
..  (2,2,1,1)  11  (1,2,2,1)  22  (2,1,1,1)  32  (1,1,2,1)  42

なお，出力例は見やすさのためにテストケースごとに余計な改行を出力していますが，これを出力する必要はありません（ただし出力しても構いません）．

Score : 2000 points

Problem Statement

Solve the following problem for T test cases.

There is a board with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Initially, all cells are colorless.

You have N^2 stamps. For each pair of integers (h,w) (1 \leq h,w \leq N), there is one stamp of size h \times w, which is called stamp (h,w). All stamps have different colors.

"Pressing a stamp (h,w)" means the following operation:

Choose a position (a,b) (1 \leq a \leq N-h+1,\ 1 \leq b \leq N-w+1). Then, color all cells (i,j) (a \leq i \leq a+h-1, b \leq j \leq b+w-1) with the color of stamp (h,w). If a cell is already colored, the color will be overwritten.

Your goal is to press each stamp exactly once so that all cells on the final board have different colors.

You have already pressed K stamps. The i-th pressed stamp was (H_i,W_i), and its position was (A_i,B_i).

Show one way to press the remaining N^2-K stamps to achieve the goal. In this problem, you are only provided with inputs where you can achieve the goal by pressing the remaining stamps in an appropriate order and positions.

Constraints

1 \leq T
2 \leq N \leq 400
0 \leq K < N^2
1 \leq H_i,W_i \leq N
1 \leq A_i \leq N-H_i+1
1 \leq B_i \leq N-W_i+1
(H_i,W_i) \neq (H_j,W_j) (i \neq j)
The sum of N^2 across all test cases in a single input does not exceed 400^2.
You are only provided with inputs where you can achieve the goal by pressing the remaining stamps in an appropriate order and positions.
All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N K
H_1 W_1 A_1 B_1
H_2 W_2 A_2 B_2
\vdots
H_K W_K A_K B_K

Output

For each test case, print an answer in the following format:

h_1 w_1 a_1 b_1
h_2 w_2 a_2 b_2
\vdots
h_{N^2-K} w_{N^2-K} a_{N^2-K} b_{N^2-K}

This means that the i-th stamp to be pressed (excluding the already pressed K stamps) is (h_i,w_i), and its position is (a_i,b_i).

Sample Input 1

Sample Output 1

Consider the first test case.

If we let i denote the color of the i-th pressed stamp (including the already pressed K stamps), the board changes as follows:

..     ->      11     ->      11     ->      31     ->      31
..  (2,2,1,1)  11  (1,2,2,1)  22  (2,1,1,1)  32  (1,1,2,1)  42

Note that the sample output includes extra newlines for readability, but you do not need to print these (although you may if you wish).