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

hamayanhamayan's blog

距離和最小 [PG BATTLE 2019 かつおぶし D]

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-4.pdf

前提知識

解説

入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください
（本番では、O(N2 logN)で出しちゃって落ちた）

公式解説

段階的に説明していこう。
貪欲解法もあるみたいだが、公式解説と同じDP解法を説明していく。

DPへの帰着 O(N3)

ここまで持ってくるのも難しい。
よくある方針で先頭から順番に決めていくという方針を今回も取ることにする。
隣り合う数だけが関係するので、
dp[i][lst] := i番目まで確定していて最後がlstであるときのコスト最小値
が作れそうな感じはする。
しかし、これではlstが109とかになり、少し難しい感じ。
よくよく考察すると、A[i]のいずれかにするのが最適であることが分かる。
というかそうじゃないとこの方針じゃ解けないなとなる。
よって、
dp[i][lst] := i番目まで確定していて最後がA[lst]であるときのコスト最小値
が出てくる。N≦5000なので、DPの形としては悪くない。
だが、これではO(N2)状態で、遷移が次のlstを全探索するのでO(N)となり、全体O(N3)となる。
dp[i][lst]からdp[i+1][lst2]の遷移の場合、

  • dp[i][lst] : 今まで
  • abs(A[lst] - A[lst2]) : 最終的に追加されるコスト（もう確定したので先に計上しておく）
  • abs(A[i] - A[lst2]) : 変更コスト

の総和がdp[i+1][lst2]となる。
まずは、このDPについて理解する必要がある。
実装するとしたら以下のようになるだろう。
最初の1つ目の遷移だけ前の要素が無いので、先にやってしまおう。

int N, A[5010];
ll dp[5010][5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N + 1) rep(lst, 0, N) dp[i][lst] = infl;
    rep(lst, 0, N) dp[1][lst] = abs(A[0] - A[lst]);

    rep(i, 1, N) rep(lst, 0, N) {
        rep(lst2, 0, N) {
            chmin(dp[i + 1][lst2], dp[i][lst] + abs(A[lst] - A[lst2]) + abs(A[i] - A[lst2]));
        }
    }

    ll ans = infl;
    rep(lst, 0, N) chmin(ans, dp[N][lst]);
    cout << ans << endl;
}

メモリ消費量がやばいので減らす 空間計算量O(N2)→O(N)

50002でlong longは256MBだとMLEする。
あるDPテーブルは1つ前の情報しか関係が無いので、テーブルを使い回すことにする。
テーブルを使い回すことで空間計算量を節約するのは常套テクなので覚えておこう。 更新前に次の領域をクリアして、更新するというのを繰り返す。

int N, A[5010];
ll dp[2][5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, 2) rep(lst, 0, N) dp[i][lst] = infl;
    rep(lst, 0, N) dp[1][lst] = abs(A[0] - A[lst]);

    rep(i, 1, N) {
        int cu = i % 2;
        int to = 1 - cu;

        rep(lst, 0, N) dp[to][lst] = infl;

        rep(lst, 0, N) rep(lst2, 0, N) {
            chmin(dp[to][lst2], dp[cu][lst] + abs(A[lst] - A[lst2]) + abs(A[i] - A[lst2]));
        }
    }

    ll ans = infl;
    rep(lst, 0, N) chmin(ans, dp[N % 2][lst]);
    cout << ans << endl;
}

更新最適化でO(N3)をO(N2)にする

さて、ここから更新の最適化になるが、いろいろな工夫をする必要がある。
まず、今は配るDPになっているので、貰うDPにする。
つまり、更新元から遷移を生やすのを考えるのではなく、更新先へ向かう遷移をひとまとめにすることで更新最適化を図る。

    rep(i, 1, N) {
        int cu = i % 2;
        int to = 1 - cu;

        rep(lst, 0, N) dp[to][lst] = infl;

        rep(lst2, 0, N) {
            rep(lst, 0, N) chmin(dp[to][lst2], dp[cu][lst] + abs(A[lst] - A[lst2]) + abs(A[i] - A[lst2]));
        }
    }

ループの順番を入れ替えただけ。
これ自体に意味が無いように見える。
ここから、chminが必要な部分を絞っていく。
まず、ループでminを探すのが必要な箇所はdp[cu][lst]+abs(A[lst]-[lst2])なので、それを分ける。

        rep(lst2, 0, N) {
            ll mi = infl;
            rep(lst, 0, N) chmin(mi, dp[cu][lst] + abs(A[lst] - A[lst2]));
            dp[to][lst2] = mi + abs(A[i] - A[lst2]);
        }

遷移をまとめる上でabsは邪魔になる場合が多い。
場合分けで分けよう。

        rep(lst2, 0, N) {
            ll mi = infl;
            rep(lst, 0, N) if (A[lst] <= A[lst2]) chmin(mi, dp[cu][lst] + A[lst2] - A[lst]);
            rep(lst, 0, N) if (A[lst] > A[lst2]) chmin(mi, dp[cu][lst] + A[lst] - A[lst2]);
            dp[to][lst2] = mi + abs(A[i] - A[lst2]);
        }

すると、A[lst2]は最小化の中には必要ないので、外に出す。

        rep(lst2, 0, N) {
            ll mi = infl, mi_less = infl, mi_more = infl;
            rep(lst, 0, N) if (A[lst] <= A[lst2]) chmin(mi_less, dp[cu][lst] - A[lst]);
            rep(lst, 0, N) if (A[lst] > A[lst2]) chmin(mi_more, dp[cu][lst] + A[lst]);
            mi = min(mi_less + A[lst2], mi_more - A[lst2]);
            dp[to][lst2] = mi + abs(A[i] - A[lst2]);
        }

これで前回の結果と定数だけのminになったので、これを高速に計算するように考える。
ここでブレイクスルーが必要になる（難しい）。
なっていてほしい状況として、配列Aが昇順に並んでいれば、この2つのminは区間minになるので、累積minを取っておけば良くなる。
ここでdpの見直しを行う。
配列Aの要素を重複を削除して、ソートした配列をBとする。
これに対し、
dp[i][lst] := i番目まで確定していて最後がB[lst]であるときのコスト最小値
を定義する。
実際、重要なのは値であって、配列Aの場所ではないので、昇順ソート済みの別配列で、数は管理することにする。
まずは、DP改造を行おう。
配列Bを用意して、配列Aは配列Bに対応した添字を入れておこう。つまり、座標圧縮と同じ操作を行う。
ソースのみやすさを配慮して、「A[lst] <= A[lst2]、A[lst] > A[lst2]」となっていたのが「A[lst] < A[lst2]、A[lst] >= A[lst2]」になっている。
等式はどちらで扱っても問題ないので、どっちでもいい。

int N, A[5010];
ll dp[2][5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<int> B = compress1(A, N);
    int M = B.size();

    rep(i, 0, 2) rep(lst, 0, N) dp[i][lst] = infl;
    rep(i, 0, N) chmin(dp[1][A[i]], 1LL * abs(B[A[0]] - B[A[i]]));

    rep(i, 1, N) {
        int cu = i % 2;
        int to = 1 - cu;

        rep(lst, 0, M) dp[to][lst] = infl;

        rep(lst2, 0, M) {
            ll mi = infl, mi_less = infl, mi_more = infl;
            rep(lst, 0, lst2) chmin(mi_less, dp[cu][lst] - B[lst]);
            rep(lst, lst2, M) chmin(mi_more, dp[cu][lst] + B[lst]);
            mi = min(mi_less + B[lst2], mi_more - B[lst2]);
            dp[to][lst2] = mi + abs(B[A[i]] - B[lst2]);
        }
    }

    ll ans = infl;
    rep(lst, 0, M) chmin(ans, dp[N % 2][lst]);
    cout << ans << endl;
}

これでやっと、区間についてのminになったので、累積和を事前に作っておくと、O(N2)が達成できる。
ガチプロはこれを15分とかで考察して正確に書き上げる。
そう。彼らにとってはこれは実家なのだから。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
vector<int> compress1(int *v, int n) {
    vector<int> dic;
    rep(i, 0, n) dic.push_back(v[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, n) v[i] = lower_bound(all(dic), v[i]) - dic.begin();
    return dic;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, A[5010];
ll dp[2][5010];
ll lft[5010], rht[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<int> B = compress1(A, N);
    int M = B.size();

    rep(i, 0, 2) rep(lst, 0, N) dp[i][lst] = infl;
    rep(i, 0, N) chmin(dp[1][A[i]], 1LL * abs(B[A[0]] - B[A[i]]));

    rep(i, 1, N) {
        int cu = i % 2;
        int to = 1 - cu;

        rep(lst, 0, M) dp[to][lst] = infl;

        rep(lst, 0, M) lft[lst] = dp[cu][lst] - B[lst];
        rep(lst, 1, M) chmin(lft[lst], lft[lst - 1]);

        rep(lst, 0, M) rht[lst] = dp[cu][lst] + B[lst];
        rrep(lst, M - 2, 0) chmin(rht[lst], rht[lst + 1]);

        rep(lst2, 0, M) {
            ll mi = infl;
            if (0 < lst2) chmin(mi, lft[lst2 - 1] + B[lst2]);
            chmin(mi, rht[lst2] - B[lst2]);
            dp[to][lst2] = mi + abs(B[A[i]] - B[lst2]);
        }
    }

    ll ans = infl;
    rep(lst, 0, M) chmin(ans, dp[N % 2][lst]);
    cout << ans << endl;
}