Educational Codeforces Round 81 E. Permutation Separation

Problem - E - Codeforces

問題概要

※解説と合わせるために0-indexedで表記します。

長さ $n$ の順列 $p_{0}, ..., p_{n-1}$ が与えられる。また $p_{i}$ を移動させるためのコスト $a_{i}$ がそれぞれ与えられる。

この順列に対して以下の処理を行う。

順列の隣り合う2要素間の境界を自由に選び、左グループと右グループに分ける。このときどちらのグループにも1つ以上の要素が含まれる必要がある。
要素を自由に選び、別のグループに移動させる操作を0回以上行う。このとき先述のコストが発生する。移動の結果どちらかのグループが空になってもよい。

この処理によって「左のグループの任意の要素は、右のグループの任意の要素よりも小さい」という状態にしたい。そのために必要な合計コストの最小値を求めよ。

制約

$2 \le n \le 2\times 10^{5}$
$p_{0}, ..., p_{n-1}$ は $0, ..., n-1$ の順列である
$1 \le a_{i} \le 10^{9}$

解法

まず、

要素を順列として与えられた順に並べたときに、最初に選ぶ左グループと右グループの境界線をどこにするか（位置の境界線）

を1つに決めたとしましょう。さらに、

要素を数の小さい方から並べ直したときに、移動後の最終状態においてどこまでが左グループに入り、大きい方からどこまでが右グループに入るか（大きさの境界線）

も決めたとします。これを以下のように図示します。

f:id:betrue12:20200130223353p:plain

位置の境界線を決めた直後に、左グループに含まれる要素を青、右グループに含まれる要素を赤に塗っています。最終的には大きさの境界線の左側が全て青に、右側が全て赤になるように色を塗り直す（つまりグループを移動する）必要があるため、そうでない要素の合計コストが必要コストになります。

では位置の境界線を1つに決めた（つまり、各要素の色が決まった）として、大きさの境界線をどのように選べば必要コストを最小にできるでしょうか。

仮に大きさの境界線が一番左にあるとすると、図中の青い要素の合計コストがそのまま必要コストになります。ここから大きさの境界線を1つずつ右にずらしていくと、追い越した要素が赤であればその要素の移動コストのぶん必要コストは増え、青であれば逆に必要コストは減る、という計算になります。

つまり注目すべきは、赤い要素をプラス、青い要素をマイナスと見た時の前からの累積和です。これが一番小さくなるような位置に大きさの境界線を持ってくるのが最適で、青い要素の合計コストにその位置での累積和を足せば必要コストになります。

f:id:betrue12:20200130220610p:plain

これで見通しがクリアになりました。あとは位置の境界線を全て試しながら、それぞれに対する最適値を求めていくことを考えます。

要素を数の小さい方から並べ、赤い要素の移動コストをプラス、青い要素の移動コストをマイナスと見て、区間 $\lbrack 0, i)$ における累積和を取った値を $S_{i}$ と書くことにします。コストを順列の順ではなく要素の値が小さい方から並び替えたものを $b_{i}$ とすると、位置の境界線が左端にある初期状態ではこれは $+b_{i}$ の累積和になります。

位置の境界線を右に1つずらすと、要素のうち1つが赤から青に変わります。この要素の値を $p$ 、そのコストを $b_{p}$ とすると、 $b_{p}$ がプラスからマイナスの扱いに変わるので、累積和においては $S_{p+1}, ..., S_{n}$ 全てに $-2b_{p}$ を足すことになります。そして必要コストの最小値は、そのときの青い要素の合計コストに $\min(S_{0}, ..., S_{n})$ を足したものです。

f:id:betrue12:20200130222223p:plain

これは区間への加算操作と区間に対する最小値取得が可能なデータ構造を用いて処理することができて、遅延伝播セグメント木などで実現することができます。

最初に分けた時にはどちらのグループにも1つ以上の要素が含まれる必要がある、という条件から、位置の境界線としては両端以外の $n-1$ 通りを試すことになります（うっかり端を含めてしまうと答えが必ず $0$ になってしまいます）。それぞれに対する必要コスト最小値の、さらに全ての最小値を取ったものが答えです。