POJ 3709: K-Anonymous Sequence

蟻本の練習です。前出た convex hull trick ですね。
ていうかこの問題だと convex hull を構成するアルゴリズムと全然関係ないですね。

問題

長さ n の単調非減少数列 a が与えられる。1 回の操作で数列の 1 つの項の値を 1 だけ小さくすることが出来る。数列の各項について, 「その項と同じ値が他に k-1 個以上ある」という性質が成り立つようにするために, 必要な最小の操作回数を求めよ。

解法

まず dp を考えていきます。

dp[i] = [0, i) で条件を満たすための最低操作回数とすると,
dp[0] = 0
dp[i] = min(dp[j] + (a[j+1]-a[j]) + ... + (a[i-1]-a[j]))(0 <= j <= i-k) ([j, i) の部分を同じ数にするという感じ)

S[i] = [0, i) における a[] の和と考えると, dp[j]+ (右) の右に書いてある値は S[i]-S[j]-(i-j)*a[j] となるので,
dp[i] = min(dp[j]+S[i]-S[j]-(i-j)*a[j])(0 <= j <= i-k) となります。

括弧の中身は j を固定すると i に関する一次式になっています。

つまり, x = i における fj(x) = dp[j]+S[i]-S[j]-(x-j)*a[j] の値が最小になる j を求めれば良い, ということになりますが, そのために deque で「[i, ∞) の区間で fj(x) の値が最小になる可能性がある直線」を管理します。

x = i で考える場合,

j の候補である i-k を追加する
fj(i) を最小にする j, 及び fj(i) を求める

ということをやります。

ひとつ目のフェーズでは, もういらなくなった([i, ∞) の区間で最小になることがありえなくなった)直線を排除して i-k を追加します。
f1, f2 という関数がこの順番で deque に登録されていて, これから f3 という関数を入れようとしているとすると, 数列 a の単調性から, (f1 の x にかかる係数) >= (f2 の x にかかる係数) >= (f3 の x にかかる係数) となります。

f2 を排除する条件が知りたいですが, これは「f1 と f3 の交点が f1 と f2 の交点より左側にある時」が必要十分です。これを排除する直線がなくなるまで続けます。

次の fj(i) を最小にする j を求めるフェーズは, deque を先頭から見ていって, 先頭が最小値じゃなかったら取り除くという作業をしていけば良いです。

const int MAXN = 500050;
ll a[MAXN], dp[MAXN], S[MAXN];
int deq[MAXN];
int n, k;

// i2 がいらない子かどうかをチェック
bool check(int i1, int i2, int i3) {
    ll a1 = -a[i1], b1 = dp[i1]-S[i1]+i1*a[i1];
    ll a2 = -a[i2], b2 = dp[i2]-S[i2]+i2*a[i2];
    ll a3 = -a[i3], b3 = dp[i3]-S[i3]+i3*a[i3];
    return (a2-a1)*(b3-b2) >= (b2-b1)*(a3-a2);
}

ll func(int i, int j) {
    return -a[j]*i+dp[j]-S[j]+j*a[j];
}

ll solve() {
    for (int i = 0; i < n; i++) S[i+1] = S[i]+a[i];
    dp[0] = 0;
    int s = 0, t = 1;
    for (int i = k; i <= n; i++) {
        if (i-k >= k) {
            // 要らなくなった直線を捨てていけ
            // 後ろから捨てていく
            while (t-2 >= s && check(deq[t-2], deq[t-1], i-k)) t--;
            deq[t++] = i-k;
        }
        while (s+1 < t && func(i, deq[s]) >= func(i, deq[s+1])) s++;
        dp[i] = S[i]+func(i, deq[s]);
    }
    return dp[n];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%lld", a+i);
        }
        printf("%lld\n", solve());
    }
    return 0;
}

mayoko’s diary

プロコンとかいろいろ。

POJ 3709: K-Anonymous Sequence

問題

解法