競技プログラミング 知識集積所

ARC226 D - Penta-Queue

五本のキュー

問題ページ解答例最悪ケース51452回解 by ちゃっぴー

考え方

クエリ $2$ は、全体の最小値をすぐにどこかのキューの先頭から出せという意味。
つまり、クエリ $1$ にしろクエリ $2$ にしろ、処理後に全体の最小値がキューの先頭にいる必要がある。

しかし、クエリ $2$ の後には入れ替え操作はできない。
つまり、クエリ $1$ の処理後に、$5$ 本のキューそれぞれがソートされた状態になっている必要がある。

ということで、考えるべきは有名なソート方法のどれを模倣するか。
作業回数的に $O(N \log N)$ のアルゴリズムをベースにした方がよさそう。
そして、部分部分はすでにソート済という状況に近しい。
これらを考えると、マージソートをベースにする方法が相性がよさそうである。

このキュー上でのマージソートは、長さ $M$ と $N$ のものをマージするのに $M+N$ 回操作が必要。
つまり、長いほど触る頻度を下げたいので、長いものへのマージはやや長めのものを一気に行いたい。
ということで、各キューの長さを等比数列的にするのがよさそう。
長さ $2$ のものは操作 $1$ 回でソートできること、最大 $5000$ 要素来ることから、以下がよい。

実際には、要素数で判定するよりもクエリ $1$ が来た回数で処理してしまったほうが実装が楽。

さて、問題はこれで回数が足りるかどうか。
最悪のケースは、明らかに、$5000$ 個の数値が降順で push されたあと $5000$ 回 pop するケース。
このとき、操作回数は以下の合計で、$66398$ 回であり、間に合う。

移動操作の総数を $M$ とすると、計算量は $O(Q+M)$。

なお、AI に調査してもらったところ、公比 $7$ というのは最善ではないそうである。
公比は $8$ の方がわずかに回数が少なく、最悪 $65624$ 回とのこと。
さらに、最初は $9$ 倍、次は $8$ 倍、次は $5$ 倍か $6$ 倍か $7$ 倍とすると、最悪 $65106$ 回とのこと。

動作例

$Q=17$ とし、push クエリで X が次の順で与えられる場合を考える。

X: 42 17 33 8 55 31 74 12 48 26 69 5 37 21 58 14 46

途中の pop クエリも含め、$17$ 回目の push クエリまでのクエリを次の順とする。
この後の残り $7$ 回の pop クエリは省略する。

1 42
1 17
1 33
2
2
1 8
1 55
1 31
2
1 74
2
1 12
2
1 48
1 26
2
2
1 69
2
1 5
2
1 37
2
1 21
1 58
1 14
1 46

最初の $2$ 回の push クエリで 42, 17 がキュー $1$ に入る。
q1_count が $2$ の倍数になるので、キュー $1$ の $2$ 個を昇順にした後、キュー $2$ へマージする。

出力
0
出力
3
1 1
1 2
1 2
キュー1:
キュー2: 17 42
キュー3:
キュー4:
キュー5:

$3$ 回目の push クエリで 33 がキュー $1$ に入る。

出力
0
キュー1: 33
キュー2: 17 42
キュー3:
キュー4:
キュー5:

その次の pop クエリでは全キューの先頭の最小値である 17 をキュー $2$ から取り除く。
もう $1$ つ pop クエリが来るので全キューの先頭の最小値である 33 をキュー $1$ から取り除く。

出力
2
出力
1
キュー1:
キュー2: 42
キュー3:
キュー4:
キュー5:

$4$ 回目の push クエリで 8 がキュー $1$ に入る。
q1_count が $2$ の倍数になるので、キュー $1$ が $2$ 個でないことを確認した後、キュー $2$ へマージする。

出力
2
1 2
2 2
キュー1:
キュー2: 8 42
キュー3:
キュー4:
キュー5:

途中を省略すると、$13$ 回目の push クエリで 37 が入った時点では次の状態になる。

キュー1: 37
キュー2: 55 69 74
キュー3:
キュー4:
キュー5:

次の pop クエリでは 37 がキュー $1$ から取り除かれる。

出力
1

ここまでの $10$ 回の pop クエリで取り除かれた値は、順に次の通り。

17 33 8 31 12 26 42 48 5 37

$14$ 回目の push クエリで 21 がキュー $1$ に入る。
この時点で残っているデータは $4$ 個で、状態は次の通り。

キュー1: 21
キュー2: 55 69 74
キュー3:
キュー4:
キュー5:

q1_count が $14$ の倍数になるので、キュー $1$ からキュー $3$ までをマージする。
今回は次の $4$ 回の移動操作を行う。

出力
4
1 3
2 3
2 3
2 3

マージ後は次の状態になる。

キュー1:
キュー2:
キュー3: 21 55 69 74
キュー4:
キュー5:

$15$ 回目の push クエリで 58 がキュー $1$ に入る。
$16$ 回目の push クエリで 14 が入り、キュー $1$ の $2$ 個を昇順にした後、キュー $2$ へマージする。

出力
0
出力
3
1 1
1 2
1 2
キュー1:
キュー2: 14 58
キュー3: 21 55 69 74
キュー4:
キュー5:

最後に、$17$ 回目の push クエリで 46 がキュー $1$ に入る。

キュー1: 46
キュー2: 14 58
キュー3: 21 55 69 74
キュー4:
キュー5:

この後は常に最小のものがどこかの先頭にいるようになっている。

注意点

インタラクティブ問題なので、各クエリへの応答を出力するたびに標準出力を flush すること。

別解

chatGPT と協力して考察したところ、最悪 $51452$ 回で済む解があることがわかりました。
ただし、これが本当の最善かどうかはわかりません。

以下は、ちゃっぴーによる解説です。

$2$ 個・$3$ 個の塊

まず、キュー $1$ に入る値を $2$ 個か $3$ 個ずつの塊として考える。
塊が完成したら、キュー $2$ から $5$ のどれかへマージする。

$2$ 個塊では、$2$ 個目が来た時点でそのままマージを始める。
キュー $1$ の小さい方が後ろにある場合だけ、自己移動を $1$ 回行う。
よって、塊の中を整えるための操作は最悪 $1$ 回。

$3$ 個塊では、$2$ 個目が来た時点でキュー $1$ の $2$ 個を昇順にしておく。
ここでは自己移動が最悪 $1$ 回必要。

$3$ 個目が来たら、キュー $1$ だけを完全にソートする必要はない。
そのまま他のキューとのマージを始める。

マージ中は、キュー $1$ から値を取り出すたびに残りを確認する。
残った値の最小値が先頭にない場合は、自己移動で先頭まで回す。

例えば、小・大・中の順に入った場合、キュー $1$ は「小 大 中」となる。
まず「小」は通常のマージ操作で取り出せる。
すると「大 中」が残るので、ここで自己移動を $1$ 回行い「中 大」とする。

この時点でキュー $1$ は最大 $3$ 個なので、必要な自己移動は合計で最大 $2$ 回。
最初の $2$ 個を整える操作と合わせて、$3$ 個塊を作るための追加操作は最悪 $3$ 回。

したがって、$3$ 個塊を作るための追加操作は最悪 $3$ 回。

塊を置く順番

$5000$ 個すべてを塊にせず、最初の $4998$ 個だけを塊にする。
最後の $2$ 個はキュー $1$ に残す。

最初の $4998$ 個は、次の $1819$ 個の塊に分ける。

実際、$1360\cdot3+459\cdot2=4998$ となる。

キュー $2$ から $5$ の $4$ 本では、長い塊ほど再びマージされる回数を減らしたい。
そこで、塊のマージ順を二分木として考える。

各頂点を $1$ 個の塊に対応させる。
根からその頂点までに左へ進んだ回数を $d$ とする。
また、右へ進む回数は最大 $3$ 回とする。

その頂点の塊は、最初のマージを含めて $d+1$ 回移動する。
一方、右へ進んだ回数が $r$ なら、マージ先をキュー $5-r$ とする。

左へ $d$ 回進んだ頂点の個数は、

$$
\sum_{r=0}^{3}\binom{d+r}{r}
=
\binom{d+4}{3}
$$

となる。

$d=0$ から $9$ までの頂点数は合計 $1000$ 個。
$d=10$ の頂点は $364$ 個。
$d=11$ の頂点は $455$ 個ある。

大きい塊ほど浅い位置に置いた方が得。
そこで、$3$ 個塊は次の位置に置く。

残りは $2$ 個塊にする。

これで $3$ 個塊が $1360$ 個、$2$ 個塊が $459$ 個になる。

実装では、この二分木を中間順でたどる。
各頂点に来たところで、対応する塊を指定されたキューへマージする。

操作回数

塊をキュー $2$ から $5$ へマージする操作回数は、

$$
3\left(
\sum_{d=0}^{9}(d+1)\binom{d+4}{3}
+360\cdot11
\right)
+2(4\cdot11+455\cdot12)
=46912
$$

回。

$3$ 個塊の中を整える操作は、最悪で $1360\cdot3=4080$ 回。

$2$ 個塊の中を整える操作は、$459$ 回。

最後にキュー $1$ に残す $2$ 個を整える操作が、最悪 $1$ 回。

したがって、移動操作の総数は最悪でも、$46912+4080+459+1=51452$ 回となる。

実際、$5000$ 個の値が降順に push された場合に、この $51452$ 回が必要になる。
途中で pop が入った場合は、後のマージで動かす要素が減る。
そのため、これより操作回数が増えることはない。