Line Chart [第七回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202107-open/tasks/past202107_h

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/past202107-open/submissions/24466156

多次元のDPをくみ上げていく。
問題設定的にはいかにもDPっぽいという感じではあるが、慣れないうちはDPテーブルの定義に戸惑うかもしれない。

なぜDPっぽい？

正直見た瞬間にDPを考え始めたので、類題を見たことがあるのだろうと思う。
と書いてもしょうがないので、すこし想像して書いてみる。

最小値を求めるという所からまずDPを考え始めた。
先頭から数を決めていくDP的な考え方をしてみると、まとめられそうな状態は総和の値と最後の値は何かという部分である。
ここでちょうど総和の上限が100であることに気が付く。
いかにもDPに収めるための条件のように見えるので、方針に自信がつき、答えとしてまとめ上げていく…

DPテーブル

DPはDPテーブルを作る所までが折り返し地点。
以下のようにテーブルを用意しよう。

dp[i][rest][lst] := i番目の要素まで確定していて、総和として残っている数がrestで、最後に選択された数がlstであるときの距離の総和の最小値

それぞれの状態数の上限が100なので、状態数だけで10⁶通りとなる。
遷移は総和の上限が100なので、選択できる数も最大100となり、遷移数は10²通りで済む。
よって、全体の計算回数は10⁸回くらいになるので、計算が軽くなりがちなDPにとっては全く問題ない計算となる。

ホントに間に合う？

実は、今回はdoubleの計算となるので、ちょっと気を付けないといけない気がする。
計算の一番深い所で距離計算をする必要があり、平方根の計算が必要になる。
この計算量で、平方根の計算が必要になるのはちょっと怖いので、この部分を前計算しておくことにする。

dist[from][to] := (i, from)と(i+1, to)の距離

これは前計算しておくのは計算量的には全く問題ないので、距離計算を毎回するのではなくこの配列を使用することで、
高速化をしておこう。

注意点として、最初と最後は0になるので、その辺をうまいことやること。
DP作れるならば、このあたりはあまり問題ではない気もする。

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

    int tot = 0;
    rep(i, 0, N) tot += A[i];

    rep(from, 0, tot + 1) rep(to, 0, tot + 1) dist[from][to] = sqrt((from - to) * (from - to) + 1);

    rep(i, 0, N + 1) rep(rest, 0, tot + 1) rep(lst, 0, tot + 1) dp[i][rest][lst] = inf;
    dp[1][tot][0] = 0;
    rep(i, 1, N - 1) rep(rest, 0, tot + 1) rep(lst, 0, tot + 1) if (dp[i][rest][lst] < inf) {
        rep(nxt, 0, rest + 1) {
            chmin(dp[i + 1][rest - nxt][nxt], dp[i][rest][lst] + dist[lst][nxt]);
        }
    }

    double ans = inf;
    rep(lst, 0, tot + 1) chmin(ans, dp[N - 1][0][lst] + dist[lst][0]);
    printf("%10f\n", ans);
}