問題概要
長さ $N$ の数列 $ A _ {i} $ が与えられる。数列の値を $1$ 変更するのにコスト $1$ がかかる。この数列を狭義単調増加列にするのに必要な最小コストを求めよ。
制約
- $1 \leq N \leq 3000$
- $1 \leq A _ {i} \leq 10^{9}$
解法
CFブログで ko_osaga 氏が言及している方針
界隈で Slope Trick と呼ばれるテクニックらしい。
始めに、数列 $ A _ {i} $ の値から予め $i$ を引いておくことで、狭義単調増加から広義単調増加を扱う問題に言い換えておく。
(余談だが、この言い換えを挟むと $ A _ {i} $ の取りうる値は $A _ {0}, \ldots ,A _ {N-1}$ に限られることを利用して O(N2) のDPで解くこともできる。実装例)
結論から述べると、この問題は次のようにして解決可能。
- 前から数列を見てコスト計算をしていく。
- 空集合、もしくは $A _ {i}$ が集合内の最大値以上の時はコスト変化無し。
- それ以外の場合は、集合内の最大値を $X$ としてコストに $X- A _ {i}$ を加算し、$X$ を集合から取り除き、代わりに $A _ {i}$ を集合に加える。
- $A _ {i}$ を集合に加える。
c++ ならば std::priority_queue
等を用いて $O(NlogN)$ で実装できる。
証明
クリックで展開
以下数列の添字は 1-indexed として扱う。
$f _ {i} (x)$ を $A _ {i} \leq x$ を満たしつつ $A[1 \ldots i]$ の範囲で広義単調増加列になるような最小コストとして定義する。これは次の数式で計算できる。
- $f _ {i} (x) = \min _ {y \leq x} (| A _ {i} - y|)$ , if i=1
- $f _ {i} (x) = \min _ {y \leq x} ( f _ {i-1} (y) + | A _ {i} - y|)$ , otherwise
式の形から明らかに、$x$ に対して $f _ {i} (x)$ は非増加列となる。
ここで、$f _ {i} (x)$ の傾きが変化する点、つまり $g _ {i} (x)= f _ {i} (x+1) - f _ {i}(x)$ として $g _ {i} (x) \neq g _ {i} (x+1)$ となるような $x$ の集合を考える。
$f _ {i} (x)$ が最小となるような最小の $x$ を $Opt(i)$ とおくと、この集合の最大値に一致し、最終的に求めるべき答えは $ f _ {N} (Opt(N))$ となる。
次に $f _ {i-1} (x)$ までの結果が求められていると仮定して、新たに $A _ {i}$ を加えた時の状態を考える。
$f _ {i} (x)$ は、絶対値関数 $h(x)=|A _ {i} -x|$ を $f _ {i-1} (x)$ に足し合わせて累積min を取った関数と見なすことができる。
ここで $A _ {i}$ の大きさに関して場合分けをする。
(1) $Opt(i-1) \leq A _ {i}$ の場合
$f _ {i} (x)$ において傾きが変化する点の集合は、$f _ {i-1} (x)$ における集合に $A _ {i}$ を加えたものになる。
傾きが変化する点の集合の最大値を考えると、$Opt(i)= A _ {i}$
従って、$f _ {i} (Opt(i))= f _ {i-1} (A _ {i}) + h(A _ {i}) = f _ {i-1} (Opt(i-1))$
(2) $Opt(i-1) \gt A _ {i}$ の場合
この場合、傾きの変化の前後に関わらず $Opt(i-1)$ において最小値を取り続ける。なぜなら、$Opt(i-1)$ は元々傾きが $-1,0$ の境界の点であるため。
よって $f _ {i} (x)$ の最小値の更新は簡単に可能で、具体的には $h(x)$ を加えたことによる差分だけを見れば良い。
つまり、$f _ {i} (Opt(i))= f _ {i-1} (Opt(i-1)) + (Opt(i-1) - A _ {i})$
続いて傾きの変化する点の集合について考える。$A _ {i}$ より左側の傾きは $-1$、右側の傾きは $+1$ され、傾きの最大値(=0)は不変であることを考慮すると、集合から $Opt(i-1)$ を1つ取り除き、$A _ {i}$ を2つ加える(前後で傾きが2変化するため)ことで辻褄が合う。
以上のことをまとめると上記で示した方針が得られる。
実装
#include <bits/stdc++.h> using namespace std; typedef long long int ll; struct SlopeTrick{ ll res; priority_queue<ll> pq; SlopeTrick():res(0),pq(){} void add(const ll x){ if(pq.size() and pq.top()>x){ res+=pq.top()-x; pq.pop(); pq.push(x); } pq.push(x); } }; int main(){ int n; cin >> n; SlopeTrick slope; for(int i=0;i<n;i++){ int a; cin >> a; a-=i; slope.add(a); } printf("%lld\n",slope.res); }
類題
- 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest C-Bookface
- 昇順ソートして $iD$ を引くと同様の問題に帰着される
- 前処理をすると数列が負の値を取る場合を除くことができる
- yukicoder No.1077 Noelちゃんと星々4
- [BalticOI 2004]Sequence 数字序列 - 洛谷
- この問題では数列の復元が求められている