bookshelf - 本棚 (Bookshelf) Editorial by Mitsubachi
はじめ、本の番号は $B_1 , B_2 , \cdots , B_N$ となっているとします。また、番号が $i$ の本を本 $i$ とします。
操作において取り出さない本を考えます。これらの本の順番は本棚の中で本を動かす際に変わりません。よって、 $x$ 冊あるとする取り出さない本の番号を左から順に $ind_1,ind_2, \cdots , ind_x$ とした際、 $ind_1 < ind_2 < \cdots < ind_x$ が成り立っていることが必要です。また、これが十分条件でもあります。
証明
便宜上 $ind_0= - \infty , ind_{x+1} = \infty$ とし、本棚の両端には番号がそれぞれ $- \infty, \infty$ である動かせない本があるとします。この時、取り出すべき本 $i$ について、 $ind_{f(i)} < i < ind_{f(i)+1}$ となる整数 $f(i)$ がただ一つ存在します。
本を取り出す際、 本 $i$ を取り出した後本 $ind_{f(i)}$ とそれより左の本を左に寄せ、それ以外の本を右に寄せることでこの $2$ 冊の間に挿入することが可能です。
よって、本 $ind_i$ と本 $ind_{i+1}$ の間にある本 $j$ について $ind_i < j < ind_{i+1}$ を成立させることが可能であり、本 $ind_i$ と本 $ind_{i+1}$ の間にある本の順番についてはどの順で本を入れたかに依存するので、本を取り出す順番を適切に工夫することで目標を達成することができます。(実際には番号の大きいものからで構いません)
さて、取り出さない本を決めた時、必要なカロリーはどうなるでしょうか。取り出す本について本を取り出す動作と戻す動作が必要なので $($ 取り出す本の重さの合計 $) \times 2$ カロリーは最低でも必要です。また、このカロリーで並び替えを完了できることもいえます。これは証明での手順を行うことで可能です。
よって、この問題は以下のように言い換えることができます。
$B$ の(非連続でもよい)単調増加な部分列 $\left( C_1 , C_2 , \cdots C_x \right)$ で、 $A_{C_1} + A_{C_2} + \cdots + A_{C_x}$ が最大となるものを求めよ。
これは末尾 \(C_x\) が \(i\) となる単調増加な部分列の中で、重さ \(A_{C_1} + A_{C_2} + \cdots + A_{C_x}\) が最大となるものを保存するセグメント木を用いることで \(O(N \log N)\) で解くことができます。
posted:
last update: