マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）F問題メモ
F - Insertion Sort
問題
- $1～N$ の順列 $P_1,P_2,...,P_N$ を、以下の方法で昇順に並べ替える
- ルール
- 好きな値を選び、それを移動させることを繰り返す
- 各値を移動させるにあたり、3つのコストが決められている
- $A_i$: 値 $i$ を好きな位置に1回移動させるコスト
- $B_i$: 値 $i$ を先頭に1回移動させるコスト
- $C_i$: 値 $i$ を末尾に1回移動させるコスト
- 必要な最小コストを求めよ
- $2 \le N \le 2 \times 10^5$
- コストは正整数
解法
好きな位置に持っていく操作を $A$、先頭に持っていく操作を $B$、末尾に持っていく操作を $C$ とする。
操作の性質
$A_i \lt B_i$ や $A_i \lt C_i$ なら先頭や末尾への移動でも $A$ を使った方がいいが、 その場合は $B_i,C_i$ を $A_i$ で上書きしておき、先頭や末尾への移動は常に $B,C$ を使うものとする。
つまり、上書きした上で $A_i \ge B_i,C_i$ と仮定をおいて問題ない。
1つの値は2回以上動かす必要は無い （もし同じ値を2回以上動かす操作手順があったとしたら、その最後の操作だけを行っても結果は変わらない） ので、結局、$1～N$ の各値に 「操作 $A$ を使う」「$B$ を使う」「$C$ を使う」「初期から移動させない」のどれかを割り振る問題となる。
移動させない値は初期から昇順に並んでいる必要があるが、コストが絡んでくるため最長増加部分列を残せばいいわけでもなく、何を残すべきか判断が難しい。
最適な移動をした場合、値は $1～N$ を順番に並べた中で3つの区間に分けられる。
- (1)$B$ を使う
- (2)動かさない、または $A$ を使う
- (3)$C$ を使う
4 1 6 3 5 2 → 2 4 1 6 3 5 2をBで移動 → 1 2 4 6 3 5 1をBで移動 → 1 2 4 3 5 6 6をCで移動 → 1 2 3 4 5 6 4をAで移動 1 2 | 3 4 5 | 6 (1) (2) (3)
必ず1つは動かさなくていい数字が存在するため、(2)は必ず存在する（(1)や(3)は、長さ0になる場合もある）。
また(2)の両端について、もしこれが $A$ によって動かされたものだとすると（$A_i \ge B_i,C_i$ の仮定があるため）、
左端なら(1)に、右端なら(3)に属させて悪くなることはない。
そのため、必ず(2)の両端は動かされていないとしてよい。
この両端を全探索すればよいのかなと思うが、そうするとそれだけで少なくとも $O(N^2)$ かかるためTLE。
一端を固定するDP
ここで、(2)の最大値だけを固定するDPを考える。
(2)の最大値を固定すると(3)の総コストは他に依らず固定されるため、その部分は最後に足してもよい。
つまり、DPで管理するのは(1)(2)部分のみでよい。
- $DP[i]=$ (2)の最大値が $i$ である時の、(1)(2)部分のみの最小コスト
$DP[1]～DP[i-1]$ から $DP[i]$ を $O(1)$ や $O(\log{N})$ 程度で計算できれば時間制約に間に合う。
最後に $DP[1]～DP[N]$ のそれぞれに(3)部分を合わせた中での最小値が答えである。
そして、$i$ が(2)の最大値になる場合というのは、以下の2通りに限られる。
値 $i$ の初期位置を $pos[i]$ とする。
- (a.) $i$ が(2)に属する最大かつ最小の数である
- つまり $1～i-1$ は $B$ で移動する
- コストは $B_1+B_2+...+B_{i-1}$
- (b.) $i$ の直前に動かさない値が $j$ であったとする
- $j$ に求められる条件は、$j \lt i$ かつ $pos[j] \lt pos[i]$
- その時、$j+1～i-1$ は全て $A$ で移動させることになり、コストは $f(j)=DP[j] + A_{j+1} + A_{j+2} + ... + A_{i-1}$
- 条件を満たす $j$ の中で、最小の $f(j)$
この中での最小値を $DP[i]$ とすればよい。
一見、(b.)の計算に各 $j$ を調べる必要があり $O(N)$ かかってしまう気がするが、
上手いことセグメント木に載せれば、区間最小値を得るクエリによって $O(\log{N})$ で可能となる。
基本的な考え方は以下の通り。
$i$ を小さい方から処理して $DP[i]$ を求めたら、その情報をセグ木の $pos[i]$ に登録する。
すると、$k$ の処理時には、セグ木の $0～pos[k]-1$ の部分に、 「$j \lt k$ かつ $pos[j] \lt pos[k]$ であるような $f(j)$ の値」が入っている状態にできるので、この最小値を求めればよい。
P 4 1 6 3 5 2
セグ木初期
0 1 2 3 4 5
INF INF INF INF INF INF
i=4 まで処理
0 1 2 3 4 5
f(4) f(1) INF f(3) INF f(2)
|-----------------------|
DP[5] について求める際は、この部分の最小値を求めればよい
だが、$f(j)=DP[j]+A_{j+1} + A_{j+2} + ... + A_{i-1}$ は、一旦登録した後でも、$i$ が進むごとに変わっていってしまう。
これは困った。もちろん毎回書き換えている時間は無い。
だが少し考えると、変化量は一旦登録された値に対しては常に一定である。
$i$ を処理するたびにセグ木全体に $A_i$ を足し込んでやれば、正しい $f(j)$ を維持できる。
その場合、区間足し込みも必要になるので、遅延評価セグメント木を使うことで実現できる。
または、「これまでに足し込まれた総和 $Add[i]=A_1+A_2+...+A_{i}$」を別に持っておいて、
- $DP[i]$ をセグ木に登録する際には $DP[i] - Add[i]$ の値を登録しておく
- $DP[i]$ を求めるためにセグ木から最小値 $min$ を取得した際は $min + Add[i-1]$ で $f(j)$ を復元する
とすると、値は登録時のまま変えずともよくなり、通常のセグメント木でも実装できるので定数倍高速になる。
