はまやんはまやんはまやん

hamayanhamayan's blog

ゴミ拾い Easy [yukicoder No.703]

https://yukicoder.me/problems/no/703

考察

1. ゴミjまで回収済みである状態があったときに誰がゴミを回収したかは特に関係ない
2. つまり、ゴミjまで回収済みであるという状態は1つにまとめることができそう
3. 動的計画法的な雰囲気が漂う
4. dp[i]はdp[0], dp[1], ..., dp[i-1]から更新できるO(N^2)
5. 出てきた更新式はCHTで高速化できる典型を適用できる
6. 解けた

解説

https://yukicoder.me/submissions/266247

この問題はCHTが分からないと解けない。
CHTを学んでから解説を読むことをおすすめする。
ちなみに、この問題はCHTの入門練習問題として良い問題である。
 
今回は配列は1-indexedで扱っていく。
dp[i] := i番目のゴミまで回収済みであるときの労力の最小値
 
まずはO(N^2)の解法を見ていこう。
dp[i] = min{0≦j<i} (dp[j] + (ゴミj+1と人iとのユークリッド距離の二乗) )
これで更新していく。
(ゴミj+1と人iとのユークリッド距離の二乗)は(A[i] - X[j+1])^2+Y[j+1]^2である。
これの最小値を順次取得していく。
 
コスト部分が二乗となっているDP更新はCHTで高速化できるという典型が存在するので、それを適用してやろう。
dp[j] + (A[i]-X[j+1])^2+Y[j+1]^2
= -2 * X[j + 1] * A[i] + X[j + 1] * X[j + 1] + Y[j + 1] * Y[j + 1] + dp[j]
このように変形して、a=-2 * X[j + 1], b=X[j + 1] * X[j + 1] + Y[j + 1] * Y[j + 1] + dp[j]とすると、
dp[i] = min{0≦j<i} (a*A[i]+b)
のようになる。「1次関数の最小値を求める」という操作はCHTで高速に行えるので、dp更新が高速化できる。

int N;
ll A[301010], X[301010], Y[301010];
ll dp[301010];
ConvexHullDynamic ch;
//---------------------------------------------------------------------------------------------------
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)
    /*rep(i, 1, N + 1) {
        ll mi = infl;
        rep(j, 0, i) {
            ll dx = A[i] - X[j + 1];
            ll dy = Y[j + 1];

            ll cst = dp[j] + dx * dx + dy * dy;
            chmin(mi, cst);
        }
        dp[i] = mi;
    }*/

    // O(NlogN)
    rep(i, 1, N + 1) {
        ch.addLine(-2LL * X[i], X[i] * X[i] + Y[i] * Y[i] + dp[i-1]);
        ll mi = ch.getBest(A[i]);
        dp[i] = mi + A[i] * A[i];
    }

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