Educational DP Contest (EDPC) A ~ E 問題 解説

#はじめに - EDPC とは
競技プログラミングを本格的にやるにあたって避けては通れない動的計画法 (DP) ですが、一言で DP と言ってもたくさんの形があり、習得するのは簡単なことではないと思います。

EDPC は、DP の典型的な問題を、基本的なものから発展的なものまで 26 題 (多い！) 集めた、いわばDPの教科書のようなものです。26 問全てを自力で解けるようになれば、少なくとも DP に関しては AtCoder 青 ~ 黄以上の実力があると言っていいと思います。(個人の見解です)

私も以前から EDPC の問題を解き進めていましたが、全ての問題を解き終わったので、この記事を書いてみることにしました。
26 題もあるので、複数の記事に分かれます。

• Educational DP Contest / DP まとめコンテスト - AtCoder

##おことわり

• ソースコードは全て C++ で書いています。
• 基本的に配列等は 0-indexed で表記、実装しています。(問題文も 0-indexed にしました)

##この記事の続き

• Educational DP Contest (EDPC) F ~ J 問題 解説
• Educational DP Contest (EDPC) K ~ O 問題 解説
• Educational DP Contest (EDPC) P ~ S 問題 解説
• Educational DP Contest (EDPC) T ~ W 問題 解説
• Educational DP Contest (EDPC) X ~ Z 問題 解説

A - Frog 1

##問題
$N$ 個の足場があります。
カエルが足場 $i$ にいるとき、カエルは次のうちどちらかの行動を行います。

• 足場 $i+1$ に移動する。コストを $|h_i-h_{i+1}|$ 支払う。
• 足場 $i+2$ に移動する。コストを $|h_i-h_{i+2}|$ 支払う。

カエルが足場 $0$ から足場 $N-1$ まで移動するための最小コストを求めてください。

##制約

• $2\leq N\leq 10^5$

##解法

「足場 $i$ までの最小コスト」を、$i$ が小さい順に求めていくことを考えます。
また、これを $dp_i$と表記することにします。最終的な答えは $dp_{N-1}$ です。
$i=0$ の時、明らかに $dp_i=0$ です。
$i\ge 1$ の時、足場 $i$ に到達する直前には足場 $i-2$ か足場 $i-1$ にいることを考えると、$dp_i=\min\left( dp_{i-2}+|h_i-h_{i-2}|,dp_{i-1}+|h_i-h_{i-1}|\right)$ です。

これを $i$ が小さい順に計算していけば、$dp_{N-1}$ を求めることができます。
時間計算量は $O(N)$ です。

##実装例

#include <iostream>
using namespace std;

const int INF = 1 << 30;

int N;
int h[100010];

int dp[100010];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    for(int i = 0; i < 100010; i++)
        dp[i] = INF;

    dp[0] = 0;
    for(int i = 1; i < N; i++) {
        dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if(i - 2 >= 0) dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[N - 1] << endl;

    return 0;
}

##別解というか、こういう書き方もあるよという話
上のソースコードと違う形のコードを書いた方もいると思うので、いくつか他の実装例も紹介します。
やっていることはどの書き方でもほぼ同じですが、問題によっては「この書き方が楽」というのがあるかもしれません。

###配る DP
因みに上に書いた方の DP は「貰う DP」というそうです 。
(余談ですが、私は記事を書く段階までこれらの名前を知りませんでした)

#include <iostream>
using namespace std;

const int INF = 1 << 30;

int N;
int h[100010];

int dp[100010];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    for(int i = 0; i < 100010; i++)
        dp[i] = INF;

    dp[0] = 0;
    for(int i = 0; i < N; i++) {
        // dp[i] から dp[i + 1], dp[i + 2] に「配る」
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
    }

    cout << dp[N - 1] << endl;

    return 0;
}

###メモ化再帰
メモ化しない再帰関数を書くとTLEしてしまうので、気を付けましょう

#include <iostream>
using namespace std;

const int INF = 1 << 30;

int N;
int h[100010];

int dp[100010];

int solve(int i) {
    if(i == 0) return 0;
    if(dp[i] != INF) return dp[i];

    int res = INF;
    res = min(res, solve(i - 1) + abs(h[i] - h[i - 1]));
    if(i >= 2) res = min(res, solve(i - 2) + abs(h[i] - h[i - 2]));
    return dp[i] = res;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    for(int i = 0; i < 100010; i++)
        dp[i] = INF;

    cout << solve(N - 1) << endl;

    return 0;
}

#B - Frog 2
##問題
$N$ 個の足場があり、足場 $i$ の高さは $h_i$ です。
カエルが足場 $i$ にいるとき、カエルは次のうちどれかの行動を行います。

• 足場 $i+1$ に移動する。コストを $|h_i-h_{i+1}|$ 支払う。
• 足場 $i+2$ に移動する。コストを $|h_i-h_{i+2}|$ 支払う。
• ......
• 足場 $i+K$ に移動する。コストを $|h_i-h_{i+K}|$ 支払う。

カエルが足場 $0$ から足場 $N-1$ まで移動するための最小コストを求めてください。

##制約

• $2\leq N\leq 10^5$
• $1\le K\le 100$

##解法
A 問題の、カエルの跳躍力が UP したバージョンです。
遷移部分 (下にもう一度書きました) を書き換える必要があります。

dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));

$dp_i$ からは $dp_{i+K}$ までのすべてにジャンプできるので、

dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
......
dp[i + K] = min(dp[i + K], dp[i] + abs(h[i + K] - h[i]));

とすればよさそうです。
$K$ は入力で与えられるので、遷移式をそのまま書くことができません。ループを使って書きましょう。
時間計算量は $O(NK)$ です。

##実装例

#include <iostream>
using namespace std;
 
const int INF = 1 << 30;
 
int N, K;
int h[100010];
 
int dp[100010];
 
int main() {
    cin >> N >> K;
    for(int i = 0; i < N; i++)
        cin >> h[i];
 
    for(int i = 0; i < 100010; i++)
        dp[i] = INF;
 
    dp[0] = 0;
    for(int i = 0; i < N; i++)
        for(int j = 1; j <= K; j++)
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
 
    cout << dp[N - 1] << endl;
 
    return 0;
}

#C - Vacation
##問題
太郎君は $N$ 回活動をします。
$i$ 回目の活動は以下のいずれかです。

• A : 幸福度を $a_i$ 得る。
• B : 幸福度を $b_i$ 得る。
• C : 幸福度を $c_i$ 得る。

$2$ 回連続で同じ行動を選ぶことはできません。
太郎君が得る幸福度を最大化してください。

##制約

• $1\le N \le 10^5$

##解法

B 問題までと同じように $dp_i$ を「$i$ 回活動したときの最大の幸福度」としてしまうと、$2$ 回連続で同じ活動をできないというルールの処理に困ります。

この問題のように取れる操作が前の操作に依存する場合、その「前の操作」の情報を添え字として管理しておくことが有効的なことがあります。今回の問題も、少し考えると、直前にどの活動をしたかがわかれば十分なことがわかります。

$dp_{i,j}$ を「次が $i$ 回目の活動で、最後に活動 $j$ をした時の最大の幸福度」とします。

添え字に持つために整数 $0,1,2$ と操作 A, B, C をそれぞれ対応させて、$C_{i,j}$ を $i$ 回目の操作 $j$ で得られる幸福度とすると、

dp_{i+1,j}=\max(dp_{i,k}+C_{i,j}) \{j\ne k\}

で求められます。出力すべき最終的な答えは $\max(dp_{N,j})$ です。
時間計算量は $O(N)$ です。

##実装例

#include <algorithm>
#include <iostream>
using namespace std;

const int INF = 1 << 30;

int N, x[100009][3];
int dp[100009][3];

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        for(int j = 0; j < 3; j++)
            cin >> x[i][j];

    for(int i = 0; i < 100009; i++)
        for(int j = 0; j < 3; j++)
            dp[i][j] = -INF;

    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for(int i = 1; i <= N; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                if(j != k) dp[i][j] = max(dp[i][j], dp[i - 1][k] + x[i][j]);

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;

    return 0;
}

#D - Knapsack 1
##問題
$N$ 個の品物があり、$i$ 番目の品物の重さは $w_i$、価値は $v_i$ です。
この中から重さの合計が $W$ 以下になるように選んだ時の、価値の合計の最大値を求めてください。

##制約

• $1\le N\le 100$
• $1\le W\le 10^5$
• $1\le w_i \le W$
• $1\le v_i\le 10^9$

##解法
この問題は非常に有名な問題で、検索すると色々な方が書いた解法が見られます。(Qiita で検索したら 140 件もヒットしました)
ここでは私がこの問題を初めて解いたときにどういう思考で解いたかを書きたいと思います。

各品物を採用するかどうか全探索すると、計算量が $O(2^N)$ となって、実行時間制限に間に合いません。
全探索のコードを再帰関数で書くと、このような感じになります。

#include <iostream>
using namespace std;

int N, W;
int w[110], v[110];

// i 番目の品物を見ている
// 残り使える重さが j
long long solve(int i, int j) {
    if(i >= N) return 0;
    long long ret = solve(i + 1, j); // i 番目を使わない遷移
    if(j - w[i] >= 0)
        ret = max(ret, solve(i + 1, j - w[i]) + v[i]); // i番目を使う遷移
    return ret;
}

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    cout << solve(0, W) << endl;

    return 0;
}

前述したとおり、もちろんこのコードではTLEとなってしまいます。
余分な計算が行われていないか考えてみましょう。 (頭の中でプログラムを回してもいいですし、コードをいじってデバッグ出力をしたりしてもいいです。)

$i$ と $j$ が同じとき、返り値が常に等しいことがわかるかと思います。
このことから、同じ $(i,j)$ の組でこの再帰関数を呼び出すのは無駄なことがわかります。
この無駄をどうなくすかというと、ここでメモ化再帰の出番です。
$(i,j)$ の組が二回目以上呼び出されたときには $dp_{i,j}$ を返すようにすればいいです。
$i,j$ はそれぞれ $O(N),O(W)$ 通りなので、計算量は $O(NW)$ となって、間に合います。

##実装例 (メモ化再帰)

#include <iostream>
using namespace std;

int N, W;
int w[110], v[110];

long long dp[110][100010];

// i 番目の品物を見ている
// 残り使える重さが j
long long solve(int i, int j) {
    if(i >= N) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    long long ret = solve(i + 1, j); // i 番目を使わない遷移
    if(j - w[i] >= 0)
        ret = max(ret, solve(i + 1, j - w[i]) + v[i]); // i番目を使う遷移
    return dp[i][j] = ret;
}

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    for(int i = 0; i < 110; i++)
        for(int j = 0; j < 100010; j++)
            dp[i][j] = -1;

    cout << solve(0, W) << endl;

    return 0;
}

##実装例 (貰う DP)
この問題はメモ化再帰以外でも解くことができます。(こっちの方がメジャーだと思うので、書いておきます。)

#include <iostream>
using namespace std;

int N, W;
int w[110], v[110];

long long dp[110][100010];

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    for(int j = 0; j <= W; j++)
        dp[0][j] = 0;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= W; j++) {
            if(j >= w[i])
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            else
                dp[i + 1][j] = dp[i][j];
        }
    }

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

    return 0;
}

#E - Knapsack 2
##問題
$N$ 個の品物があり、$i$ 番目の品物の重さは $w_i$、価値は $v_i$ です。
この中から重さの合計が $W$ 以下になるように選んだ時の、価値の合計の最大値を求めてください。

##制約

• $1\le N\le 100$
• $1\le W\le 10^9$
• $1\le w_i\le W$
• $1\le v_i\le 10^3$

##解法
一見、D 問題と全く同じ問題に見えますが、制約が異なっています。
さっきと同じ解法だと、計算量が $O(NW)$ なので、余裕で間に合いません。

制約を眺めていると、$v$ が小さいことに気づきます。問題 D では $N$ と重さに関する情報を添え字に持っていたので、添え字に持つ情報を変えればいいのではないかという発想に至ります。

$dp_{i,j}$ を、「次に見るのが $i$ 番目で、合計価値が $j$ 以上である状態にするための、重さの合計の最小値」として、DP します。
遷移に関しては、D 問題と同じ感じでやれば大丈夫です。 (わからない場合は実装例を参照してください)

$V=\max(v_i)$ とすると、$j\le NV$ より、DP テーブルの状態数は $O(N^2V)$ です。
遷移は $O(1)$ なので、全体の計算量は $O(N^2V)$ で、十分高速です。

正解例

#include <iostream>
using namespace std;

const long long INF = 1LL << 60;

int N, W;
int w[110], v[110];

long long dp[110][100010];

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    for(int i = 0; i < 110; i++)
        for(int j = 0; j < 100010; j++)
            dp[i][j] = INF;

    dp[0][0] = 0;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= 100000; j++) {
            if(j >= v[i])
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
    }

    int res = 0;
    for(int j = 0; j <= 100000; j++)
        if(dp[N][j] <= W) res = j;

    cout << res << endl;

    return 0;
}

#続き
ここまで自力でできた方は、ぜひこれ以降の問題も解いてみましょう。

• Educational DP Contest (EDPC) F ~ J 問題 解説