第三回 アルゴリズム実技検定

• 問題
• 提出

リアルタイム受験した。A～Nを解いて辛うじてエキスパートだった。（しかもNはオーダー的に間違っていると知りつつ枝刈りで通した……）

K

次の4つの配列を持ってシミュレーションする:

• $\operatorname{bottom}[x] :=$ 机$x$の一番下にあるコンテナ
• $\operatorname{top}[x] :=$ 机$x$の一番上にあるコンテナ
• $\operatorname{prev}[y] :=$ コンテナ$y$の下にあるコンテナ
• $\operatorname{next}[y] :=$ コンテナ$y$の上にあるコンテナ

もっと楽にできるらしい。

L

優先度付きキューを二つ用意して、一つは先頭の商品全部が入っている状態を保ち、もう一つは二番目までの商品全部が入っている状態を保つ。（どちらかのキューに既に買われた商品が残っている、は問題ない。買われたものを記録しておいて、既に買われたものを取り出した場合は飛ばせばよい）

N

$x$をスワップするクエリが来ると、区間$[x, x+1]$の順序が乱れる。順序が乱れたところを記録しておいて、ソートクエリが来たらそこだけソートすればよさそうだが、計算量的に「正しい」やりかたを書けなかった。例えば$[10, 30], [40, 50], [100, 120]$が乱れているとして、$[20, 110]$のソートクエリが来たら、$[20, 30], [40, 50], [100, 110]$だけソートすればよい……のだが、それによって正しい順序に戻るのは$[40, 50]$だけで、$[10, 30], [100, 200]$は全体としては乱れたままなのが困りごとだった。（つまり、素朴にやると中途半端な区間を何度もソートさせるような入力でオーダーが改善していない。）　この例でいうと、$[10, 30]$のうち$[20, 30]$がソートされたら、もう一度$[20, 30]$や$[21, 30]$のソートクエリが来ても何もする必要がないとか、列を平衡二分木などで保持しておいて、$[18, 30]$のソートクエリが来た時に、$a_{19}, a_{18}$だけ挿入しなおすような処理ができればならしで間に合っているとか、部分的なアイデアは思いつくものの全体としてうまく動くようにまとめきれなかった。（しかし、終了直前に不完全なまま出したら通ってしまった。）

「中途半端なソート」でも転倒ベースで見ればうまく扱える、確かに。しかし、それでも実装はまあまあ大変に見える。