Bookshelf(本棚) - joi2011-day4 解説

筆者: qnighy

本棚に本が一列に並んでいて、番号と重みが決められているとき、「ある本を取り除いて、任意の位置に再度挿入する」をその本の重み(の2倍)をコストとして実行できるとして、最小コストで本を番号通りの順番に戻す問題である。

解析

以下の事実に気づくことが重要である。

後者を証明しよう。

(→) Sに属する本は動かしていないのだから、それらの間の順序は変化していないはずであるから、当然元から昇順であったはずである。■

(←) Sに属さない本を、1番の本から順番に移動するだけでよい。■

さらに、Sの重みの和と、移動に必要なコストは、線形の負の相関関係にあることが明らかであるから、条件を満たすSのなかで重み最大のものを考えればよい。

名前を付けるのであれば、「重み最大増加部分列」となるだろう。

w=1のとき有名な最長増加部分列問題であるので、単純な動的計画法を用いることで20点を得られる。

同様に、最長増加部分列は二分探索を用いてO(NlogN)で書けることが知られている。これで30点が得られる。なお、wが1とは限らないときのO(N^2)の解法は省略する。

列を左側から順番に処理することを考える。各状態で

「今まで処理した列のなかで、i番の本を末尾にすえた部分列のうち重み最大のもの」

を記録していく。

すると、次の本がxだったとき、i<xなる本を末尾にすえた部分列のうち重み最大のものに本xを加えたものがその時点での最大として得られる。

つまりこれは、配列上の「特定の値の最大値更新」と「0からある範囲までの間の最大値取得」ができるデータ構造を必要としている。これを実現するために、RMQまたはmaxに対するFenwick Treeを使うことができる。

以上を実装することで満点が期待できる。