かっつのメモ帳

主に競プロ　時々日記

Codeforces Round #371 (Div. 1) C-Sonya and Problem Wihtout a Legend

競プロ Slope Trick

問題のリンク

問題概要

長さ $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);
}

類題