ABC201-Fを解いた
問題
順列に対して、次の操作を繰り返し
を狭義単調増加にする。コストの最小値は?
- を満たす
を選択し、
を好きな位置に移動させる。
- を満たす
を選択し、
を左端に移動させる。
- を満たす
を選択し、
を右端に移動させる。
かかるコストは上から順にである。
解法
一番上の操作は下二つの操作の上位互換であるため、に
を、
に
を代入してよい。
一回も操作をしないindexの集合をを決めると、そのほかのindexに対する操作が一意に定まる。(具体的には、
を満たす
については左端への、
を満たす
については右端への、そうでない場合は自由な挿入の操作を選択する)
ここで、
を考えると、の順に
という遷移ができるが、このままでは間に合わない。これは最初に答えにを加算して置き(詳しくは実装を)、その差分を計算することを考え、区間min取得/一点更新ができるSegmentTreeを用いれば
で解が求まる。
考察
あんまり動かしたくない->動かさないものは単調増加->動かさないのに注目すればよさそう?
