AGC032-D:Rotation Sort - 思考の墓場

やっぱりAGCの問題は綺麗で良いなあ...。

問題

解法

　Rotation操作はややこしいので、言い換えを考える。よく眺めると、右シフトは「好きな数を今の位置より右側の好きな位置に移す」と言い換えられる。左シフトも同様なので、結局

「コスト $A$ を払い、好きな数を今の位置より右側の好きな位置に移す」
「コスト $B$ を払い、好きな数を今の位置より左側の好きな位置に移す」

とい2つの操作を考えればよい。この操作ができるとき、ソートに必要なコストの最小値を求めることが求められている。

　さて、sortするのに必要な最小コスト(または操作回数)を求める場合、dpを考えると有効な場合がある。特に、小さい数字からどの(相対的な)位置に置くか？ということを決めていくdpを考えるとうまくいきそうな気がしてくる。例えば、 $1\sim i-1$ までは昇順に並んでいるとすれば、 $i$ をどの位置に置くべきかは $i-1$ との位置関係だけを見れば十分になるというのは都合が良いだろう。従って、dpの状態として「 $1$ から $i$ までは昇順に並んでいる」ということを持つことにする。もちろんこれだけでは不十分である。なぜ不十分かというと、 $i$ より大きい数も含めたときに、全体としてどれくらい揃っているかということも重要だからである。ここでどういう情報を持つとよいかは難しいが、筆者は「 $i$ より手前の位置にあって、 $i$ より大きい数が $j$ 個ある」という情報を持った。まとめると

$dp_{i,j}$ : $1$ から $i$ までの数は昇順に並んでいて、 $i$ より左側にあって $i$ より大きい数が $j$ 個あるような順列にするときの、操作コストの最小値」

としてdpを行うことにした。
　遷移を考えよう。まず、各数に行う操作は「左に動かす」「右に動かす」「動かさない」でいずれかを $1$ 回のみでよいのは明らかだろう。さらに、dpの遷移の際には $i-1$ までは昇順に並んでいるとしているので、以下のように考えてよい。

$i-1$ が $i$ より左側にあるときに $i$ に行う操作は「左に動かす」か「動かさない」
$i-1$ が $i$ より右側にあるときに $i$ に行う操作は「右に動かす」

つまり、 $i-1$ と $i$ の位置関係が管理できれば遷移が可能になる。そこで、 $l_i$ :元の順列 $\{p_i\}$ に関して、 $i$ より左側にあり $i$ より大きい数の個数　とする。すると、 $i-1$ から $i$ への遷移について、 $j \leq l_i$ のときは $1$ に該当し、そうでないときは $2$ に該当することがわかる。よって、以下のような遷移式が書ける。