ゴミ拾い Medium [yukicoder No.704] - はまやんはまやんはまやん

前提知識

セグメントツリー

考察

1. この問題と似ているので、動的計画法で考える
2. とりあえずO(N^2)を書く
3. 絶対値を取る操作がやっかいなので場合分けしてみると、セグメントツリーで高速化できそうになる
4. 解けた

解説

この問題と同じく動的計画法で解いていこう。
今回は配列は1-indexedで扱っていく。
dp[i] := i番目のゴミまで回収済みであるときの労力の最小値
　
まずはO(N^2)の解法を見ていこう。
dp[i] = min{0≦j＜i} (dp[j] + (ゴミj+1と人iとのマンハッタン距離) )
これで更新していく。
(ゴミj+1と人iとのマンハッタン距離)はabs(A[i] - X[j + 1])+Y[j + 1]である。
これの最小値を順次取得していく。
　
絶対値の扱いがとても面倒なので、場合分けして絶対値を消そう。
dp[i] = min{0≦j＜i} ( A[i] - X[j + 1]+Y[j + 1] ) A[i]≧X[j+1]
　　　　　　　　　( X[j + 1] - A[i]+Y[j + 1] ) A[i]＜X[j+1]
これではまだ計算量がO(N^2)のまま落ちていない。
　
場合分け先を見てみると、
A[i]≧X[j+1]の場合は(-X[j+1]+Y[j+1])の最小値+A[i]
A[i]＜X[j+1の場合は(X[j+1]+Y[j+1])の最小値-A[i]]
を計算すればいい。
この最小値部分は区間minセグメントツリーで高速に取ってこれる。
「今までのゴミの(-X[j+1]+Y[j+1])が入ったセグメントツリーの[0,A[i]]でのmin+A[i]」
「今までのゴミの(X[j+1]+Y[j+1])が入ったセグメントツリーの[A[i], inf]でのmin-A[i]」
これを計算して更新していくとO(NlogN)まで高速化できる。
A[i]やX[i]が10^9とかになるので、動的セグメントツリーを使うか、座圧して乗せよう。
以下のコードではA[i],X[i]を座圧して普通の区間minセグメントツリーで実装している。

int N;
ll A[301010], X[301010], Y[301010];
ll dp[301010];
SegTree<ll, 1 << 20> st1, st2;
vector<int> dic;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) cin >> A[i];
    rep(i, 1, N + 1) cin >> X[i];
    rep(i, 1, N + 1) cin >> Y[i];

    rep(i, 0, N + 1) dp[i] = infl;
    dp[0] = 0;
    
    /* O(N^2) ver1
    rep(i, 1, N + 1) {
        rep(j, 0, i) {
            ll dx = abs(A[i] - X[j + 1]);
            ll dy = Y[j + 1];
            ll z = dp[j] + dx + dy;
            chmin(dp[i], z);
        }
    }*/

    /* O(N^2) ver2
    rep(i, 1, N + 1) {
        rep(j, 0, i) if (A[i] < X[j + 1]) chmin(dp[i], dp[j] + X[j + 1] - A[i] + Y[j + 1]);
        rep(j, 0, i) if (A[i] >= X[j + 1]) chmin(dp[i], dp[j] + A[i] - X[j + 1] + Y[j + 1]);
    }*/

    rep(i, 1, N + 1) dic.push_back(A[i]);
    rep(i, 1, N + 1) dic.push_back(X[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());

    rep(i, 1, N + 1) {
        int x = lower_bound(all(dic), X[i]) - dic.begin();
        int a = lower_bound(all(dic), A[i]) - dic.begin();

        st1.update(x, min(st1[x], dp[i - 1] + X[i] + Y[i]));
        st2.update(x, min(st2[x], dp[i - 1] - X[i] + Y[i]));

        chmin(dp[i], st1.get(a, 1 << 20) - A[i]);
        chmin(dp[i], st2.get(0, a) + A[i]);
    }

    cout << dp[N] << endl;
}