JOI 2008 本選4 ぴょんぴょん川渡り - 解説

アルゴリズム

• 動的計画法

  問題

D - ぴょんぴょん川渡り

石の滑りやすさと石の場所が与えられるので対岸へ石を渡っていくときの危険度の最小値を求めなさい

愚直に考える

「今いる石から移ることのできる石へ移動する」を繰り返すことで答えは求まります これを愚直にシミュレーションすると、行目にいる時個の石へ移動することができ、計算量が膨大になりTLEになってしまいます

動的計画法(DP)

「今いる石(行目)までの危険度の最小値」が分かれば行目の石までの危険度の最小値も計算することができ、これを繰り返すことでこの問題の解を出すことができます

１マス飛ばしのジャンプの回数制限

さらに考察します この問題では１マス飛ばしのジャンプが回しかできないという制約があります そこでdpテーブルの添字に「今いる石に到達するまで何回１マス飛ばしのジャンプをしたか」の情報を持たせるようにします

漸化式

今見ている石が存在する行

今見ている石が存在する列

今見ている石に到達するまで何回１マス飛ばしのジャンプをしたか

とすると漸化式は次のようになります

となります(dpテーブルは十分に大きい数で初期化) 動的計画法によりでこの問題を解くことができます

コード

答えは

になります

↓サンプルコード(include defineなどは省略)

void Main() {
    int n, m;
    cin >> n >> m;
    vvi stone(n, vi(1001));
    vector<vector<bool>> exist_stone(n, vector<bool>(1001, false));
    rep(i, n) {
        int k;
        cin >> k;
        rep(j, k) {
            int x, d;
            cin >> x >> d;
            x--;
            stone[i][x] = d;
            exist_stone[i][x] = true;
        }
    }
    vvvi dp(n, vvi(1001, vi(m + 1, INF_I)));
    rep(i, 1001) {
        if (exist_stone[0][i])
            dp[0][i][0] = 0;
        if (exist_stone[1][i])
            dp[1][i][1] = 0;
    }
    reps(i, n - 1) {
        rep(j, 1001) {
            if (!exist_stone[i][j])
                continue;
            rep(k, 1001) {
                rep(l, m + 1) {
                    if (exist_stone[i - 1][k])
                        chmin(dp[i][j][l], dp[i - 1][k][l] + (stone[i - 1][k] + stone[i][j]) * abs(k - j));
                    if (i >= 2 && exist_stone[i - 2][k] && l >= 1)
                        chmin(dp[i][j][l], dp[i - 2][k][l - 1] + (stone[i - 2][k] + stone[i][j]) * abs(k - j));
                }
            }
        }
    }
    int ans = INF_I;
    rep(i, 1001) {
        rep(l, m + 1) {
            chmin(ans, dp[n - 1][i][l]);
            if (l < m)
                chmin(ans, dp[n - 2][i][l]);
        }
    }
    cout << ans << endl;
}

筆者の提出

atcoder.jp

問題を部分部分に分け、それらの問題の答えが利用できる場合はDPを考えましょう