初めに

とりあえず初めに動的計画法のWikipediaを貼っておきます。

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

この記事はDP初心者の私がDPを触ったことのない人に向けて、問題を解く上で気が付いたことや、問題を1から解いた際の考え方の道筋を説明しようと試みた記事です。今回解いた問題は全部で10問です。

1問目フィボナッチ数列

実行時間制限($1\sec$)

フィボナッチ数列の第$n$項の値を出力するプログラムを作成してください。ここではフィボナッチ数列を以下の再帰的な式で定義します：
$$
\begin{equation*} fib(n)= \left \{ \begin{array}{ll} 1　 & (n = 0) \\ 1　 & (n = 1) \\ fib(n - 1) + fib(n - 2) & \\ \end{array} \right. \end{equation*}
$$

DPの勉強を始めたときに一番初めに出てきた問題です。フィボナッチ数列は再帰関数の実装やらを勉強している際に出てきますが、実際に再帰関数を使って実装すると次のようになります。

fib.cpp

int fib(int n) {
    if(n == 0 || n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

正しいには正しいですがこのコードはTLEとなってしまいます。$n=44$の時に1秒以上かかってしまうからです。計算量が$n$の増加とともに爆発的に増えてしまうのは無駄な計算を何度も何度も行っているからで、これを改善するには一度計算したものをメモしておけばよいです。AC解答

...といった感じで、
フィボナッチ数列の問題は恐らくメモ化の導入ということで再帰で書いて、それを改善して、というステップを踏んでいると思うのですが、これによって私はこの問題のもう一つの重要なポイントに気が付けなかったのでメモ化の詳しい話は置いといてそれを先に説明します。(私の頭が固いだけの可能性は大いにありますが...)

この問題で注目すべきもう一つの点とは「フィボナッチ数列が再帰的な式で定義されている」ということです。

$$
\begin{equation*} fib(n)= \left \{ \begin{array}{ll} 1　 & (n = 0) \\ 1　 & (n = 1) \\ fib(n - 1) + fib(n - 2) & \\ \end{array} \right. \end{equation*}
$$

これですね。

実は再帰を使わなくともこの漸化式を見たまんまプログラムに落とし込むことでAC解答を得ることができます。

fib.cpp

#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<int> fib(n + 1);

    fib.at(0) = 1;
    fib.at(1) = 1;
    for(int i = 2; i <= n; ++i)
        fib.at(i) = fib.at(i - 1) + fib.at(i - 2);

    std::cout << fib.at(n) << std::endl;
    return 0;
}

ほんとに見たまんまですね。問題が漸化式で表されているならそれをそのままプログラムにすることで問題が解けてしまうというわけです。元々与えられてるせいで私は全く気が付きませんでしたが、実はこれがとても嬉しいことだったんですね。

ということで、問題をDPで解くときの指針を「問題を漸化式に落とし込む」としていくつか見ていきたいと思います。

2問目 Frog 1

実行時間制限($2\sec$)

$N$個の足場があります。足場には$1,2,…,N$と番号が振られています。各$i(1≤i≤N)$について、足場$i$の高さは$h_i$です。最初、足場$1$にカエルがいます。カエルは次の行動を何回か繰り返し、足場$N$まで辿り着こうとしています。

足場$i$にいるとき、足場$i+1$または$i+2$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$∣h_i−h_j∣$を支払う。

カエルが足場$N$に辿り着くまでに支払うコストの総和の最小値を求めてください。

この問題を再帰的な式で表現することを考えます。つまり直前の情報をもとに答えを求められるかを考えるわけです。

この問題文から自然に得られる足場$N$の直前の情報を見てみると

足場$N-1$からジャンプした場合のコスト
足場$N-2$からジャンプした場合のコスト

です。これらの大小は簡単に求められます。しかし、これだけでは足場$N$までに支払うコストの総和の最小値は求められません。そこで、この情報に何が加われば目的の情報を得られるかを考えます。

入力例$1$を例に見てみると

4
10 30 40 20

足場$4$直前の情報は

足場$2$,$3$から足場$4$へ飛び移るためのコストは$2 \rightarrow 4$のとき$10,$ $3 \rightarrow 4$のとき$20$

です。足場$4$までに支払うコストの総和の最小値を求めるときに欲しい情報といったらもう足場$1$から足場$2$, $3$に飛び移るときのコストですね。

つまり、足場$N$までに支払うコストの総和の最小値を求める際に欲しい情報は

足場$N-1$と$N-2$までに支払うコストの総和の最小値

というわけです。足場$N$までに支払うコストの総和の最小値を$N_{min}$と表現すれば

$N_{min} = min(N-1_{min} + |h_n - h_{n-1}|, N-2_{min} + |h_n - h_{n-2}|)$

であると分かります。

さて、ここまで来たら定数を探します。再帰関数でもそうですが終点が必要ですね。入力の最初の方に以前の結果によらずコストの総和が一定のものは無いかを探します。
今回であれば足場$1$までに支払うコストの総和は$0$、足場$2$までに支払うコストの総和は$|h_2-h_1|$でそれまでの結果によらずに一定になっています。

これまでの考えをまとめると、この問題は再帰的な式で表すことができて、次のようになります。

$$
\begin{equation*} f(n)= \left \{ \begin{array}{lll} 0　 & (n = 1) \\ |h_2-h_1|　 & (n = 2) \\ min(f(n-1) + |h_n-h_{n-1}|, f(n-2) + |h_n-h_{n-2}|) & (n \geq 3) \\ \end{array} \right. \end{equation*}
$$

式で表すことができれば後は実装するだけなので、これでACとなります。

frog1.cpp

#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<int> h(n);
    for(auto& i: h) std::cin >> i;
    
    std::vector<int> f(n);
    f.at(0) = 0;
    f.at(1) = std::abs(h.at(1) - h.at(0));
    for(int i = 2; i < n; ++i) {
        f.at(i) = std::min(
            f.at(i - 1) + std::abs(h.at(i) - h.at(i - 1)),
            f.at(i - 2) + std::abs(h.at(i) - h.at(i - 2))
        );
    }
    std::cout << f.at(n - 1) << std::endl;
    return 0;
}

3問目 Vacation

実行制限時間($2\sec$)

明日から太郎君の夏休みが始まります。太郎君は夏休みの計画を立てることにしました。夏休みは$N$日から>なります。各 $i (1≤i≤N)$について、$i$日目には太郎君は次の活動のうちひとつを選んで行います。

A: 海で泳ぐ。幸福度$a_i$を得る。

B: 山で虫取りをする。幸福度$b_i$を得る。

C: 家で宿題をする。幸福度$c_i$を得る。

太郎君は飽き性なので、$2$日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

これもとりあえず$N$日目に得られる直前の情報を整理します。

$N-1$日目に行った活動の幸福度
- $a_{n-1}$ or $b_{n-1}$ or $c_{n-1}$
$N-1$日目と$N$日目の2日間の活動で得られる幸福度の総和の最大値
- $N-1$日目でAを選ぶなら$a_{n-1} + max(b_n, c_n)$

これに何かしらの情報を加えて$N$日目までの幸福度の総和の最大値を求められないかを考えます。これも入力例を見ながら考えてみましょう。

3日目直前の情報は

Aを選んだ場合幸福度$20$, Bなら$50$, Cなら$80$
$2$日目と$3$日目の幸福度の総和の最大値は$2$日目でAを選んだ時は$110$, Bなら$140$, Cなら$140$

ですね。$3$日目までの幸福度の総和を最大にするためには$2$日目でA, B, Cそれぞれを選んだ場合の幸福度の総和の最大値が欲しいです。

つまり、$N$日目までの幸福度の総和の最大値を求めるに必要な情報は

$N-1$日目で活動A, B, Cを選んだ場合の幸福度の総和の最大値

というわけです。$N-1$日目で活動B, Cを選んだ時の幸福度の総和の最大値が分かっていれば、$N$日目で活動$A$をしたときに得られる幸福度の総和の最大値を$A_N$と表現したとき

$A_N = a_n + max(B_{N-1}, C_{N-1})$

であると分かります。
定数は$1$日目のA, B, Cを選んだ場合の幸福度の総和が$a_1$, $b_1$, $c_1$で定数になっているためこれを使えばよいです。

これまでの考えをまとめると、この問題も再帰的な式で表すことができて、次のようになります。

$$
\begin{equation*}
f(n) = \left \{ \begin{array}{ll} (a_1, b_1, c_1)　 & (n = 1) \\ (a_n + max(B_{n-1},C_{n-1}),b_n + max(A_{n-1},C_{n-1}),c_n + max(A_{n-1}, B_{n-1}))　 & (n \geq 2) \\ \end{array} \right. \end{equation*}
$$

そのまま実装するとACになります。

vacation.cpp

#include <iostream>
#include <vector>
struct Vacation {
    int a, b, c;
};
int max(Vacation v) {
    if(v.a > v.b && v.a > v.c) return v.a;
    if(v.b > v.a && v.b > v.c) return v.b;
    else return v.c;
}
int main() {
    int n; std::cin >> n;
    std::vector<Vacation> qol(n);
    for(auto& v: qol) std::cin >> v.a >> v.b >> v.c;

    std::vector<Vacation> dp(n);
    dp.at(0) = qol.at(0);
    for(int i = 1; i < n; ++i) {
        const auto [a, b, c] = qol.at(i);
        const auto [A, B, C] = dp.at(i - 1);

        dp.at(i) = { a + std::max(B, C), b + std::max(A, C), c + std::max(A, B) };
    }

    std::cout << max(dp.at(n - 1)) << std::endl;
    return 0;
}

4問目 Jumping Takahashi

実行制限時間($2\sec$)

高橋君は数直線上の座標$0$の位置にいます。
これから高橋君は$N$回のジャンプを行います。$i(1≤i≤N)$回目のジャンプでは、正の方向に$a_i$または$b_i$移動します。$N$回のジャンプの後に座標$X$の位置にいるようにすることはできますか？

とりあえず何も考えずに最後の行動の直前の情報を書きだすと

$N$回目のジャンプで移動してきた距離

です。これでは$N$回のジャンプの後に座標$X$の位置にいるかなんて到底分からないので、何か情報を足すことを考えましょう。ここから、$N$回のジャンプを終えた時点での座標を求めようと思ったら

$N-1$回目のジャンプを終えた時点で高橋君がいる可能性のあるすべての座標

があれば十分です。それぞれの座標から$N$回目のジャンプで移動した際の位置を調べていき$X$と比べれば分かります。

この場合、$i$回目のジャンプが終了した時点での情報量は$i-1$回目のジャンプが終了した時点での情報量の$2$倍になるので今までのように$1$次元配列で処理するのはちょっと無理そうです。
($1$回目の時点では$a_1$, $b_2$のみですが$2$回目終了時点では$a_1+a_2$,$a_1+b_2$,$b_1+a_2$,$b_1+b_2$の4通り、$3$回目では$8$通り...と増えていきます)

ということで、$2$次元配列を使います。$i$回目のジャンプを終えた時点でいる可能性のある座標を$j$とした2次元配列で表現すれば良さそうですね。

$i$回目のジャンプを終えた時点で座標$j$の位置にいることができるならtrue, 無理ならfalseとし、定数は$1$回目のジャンプの移動先で良さそうなのでこれをもとに式で表すと以下のようになります。

$$
\begin{equation*}
dp[i][j] = \left \{ \begin{array}{lll} 1 & (i=0, j=a_1, b_1) \\ 1 & (dp[i-1][j-a_{i}]=1 \lor dp[i-1][j-b_{i}]=1) \\ 0　 & (dp[i-1][j-a_i]=0 \land dp[i-1][j-b_i]=0) \\ \end{array} \right. \end{equation*}
$$

添え字が$i$である方の要素数は$N$で良いとして$j$である方の要素数はどのように決めればよいでしょうか。情報量はどんなに小さくとも$2^N$ですので、制約の$1 \leq N \leq 100$と$1 \leq a_i \leq b_i \leq 100$を考えると全通り記録しておくには確保しなくてはならない配列の大きさが現実的ではありません。

上を何で抑えればよいかというと、結果が$X$以下におさまっているものだけを調べればよいので、添え字が$j$である方の要素数は$X+1$とすればよいです。

あとは配列の範囲外にアクセスしないことと、配列をfalseで初期化することに気を付けて実装すればOKです。

jump.cpp

#include <iostream>
#include <vector>
struct Jump{ int a, b; };
int main() {
    int n, x; std::cin >> n >> x;
    std::vector<Jump> jump(n);
    for(auto& i: jump) std::cin >> i.a >> i.b;

    std::vector<std::vector<bool>> dp(n, std::vector<bool>(x + 1, false));
    if(int a = jump.at(0).a; a <= x) dp.at(0).at(a) = true;
    if(int b = jump.at(0).b; b <= x) dp.at(0).at(b) = true;
    for(int i = 1; i < n; ++i) {
        const auto [a, b] = jump.at(i);
        for(int j = 0; j < x + 1; ++j) {
            if(j - a >= 0) dp.at(i).at(j) = dp.at(i - 1).at(j - a);
            if(j - b >= 0) dp.at(i).at(j) = dp.at(i - 1).at(j - b) || dp.at(i).at(j);
        }
    }
    if(dp.at(n - 1).at(x)) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    return 0;
}

これは初めから決まった大きさのbool型の$2$次元配列を使っていますが、当初の解き方

$N-1$回目のジャンプを終えた時点で高橋君がいる可能性のあるすべての座標

があれば十分です。それぞれの座標から$N$回目のジャンプで移動した際の位置を調べていき$X$と比べれば分かります

をそのまま実装してみるとどうなるでしょうか、余談なので折りたたんでしまいますが、プログラム自体は以下のようになるはずです。

移動先の座標を記録するパターン1

#include <iostream>
#include <vector>
struct Jump{ int a, b; };
int main() {
    int n, x; std::cin >> n >> x;
    std::vector<Jump> jump(n);
    for(auto& i: jump) std::cin >> i.a >> i.b;

    std::vector<std::vector<int>> dp(n);
    dp.at(0).push_back(jump.at(0).a);
    dp.at(0).push_back(jump.at(0).b);
    for(int i = 1; i < n; ++i) {
        const auto [a, b] = jump.at(i);
        for(const auto c: dp.at(i - 1)) {
            if(c + a <= x) dp.at(i).push_back(c + a);
            if(c + b <= x) dp.at(i).push_back(c + b);
        }
    }
    for(const auto& l: dp.at(n - 1)) {
        if(l == x) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;
    return 0;
}

一見正しそうですが、残念ながらこれはTLEとなります。先ほどと同じコードに見えるのになぜTLEになってしまうのかというと、それは全く同じ座標を何度も重複して追加してしまっているからです。

$2$次元配列を使うと決め、それをそのままプログラムに落とし込んだ時には全く意識していませんでしたが、あの方針では異なる位置からのジャンプ先が重複していても計算量は変わりません。しかし、このコードはジャンプ先の座標が$X$以下なら、重複してようがしてまいがどんどん追加してしまっています。

つまりどうすれば良いかというと重複する要素の挿入をなくせばいいのでsetを使えばいいです。

移動先の座標を記録するパターン2

#include <iostream>
#include <vector>
#include <set>
struct Jump{ int a, b; };
int main() {
    int n, x; std::cin >> n >> x;
    std::vector<Jump> jump(n);
    for(auto& i: jump) std::cin >> i.a >> i.b;

    std::vector<std::set<int>> dp(n);
    dp.at(0).insert(jump.at(0).a);
    dp.at(0).insert(jump.at(0).b);
    for(int i = 1; i < n; ++i) {
        const auto [a, b] = jump.at(i);
        for(const auto c: dp.at(i - 1)) {
            if(c + a <= x) dp.at(i).insert(c + a);
            if(c + b <= x) dp.at(i).insert(c + b);
        }
    }
    for(const auto& l: dp.at(n - 1)) {
        if(l == x) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;
    return 0;
}

これはACとなります。

5問目コイン問題

実行時間制限($1\sec$)

額面が$c_1, c_2,..., c_m$円の$m$種類のコインを使って、$n$円を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。

いつも通り$n$円ちょうど支払える直前の状態を考えます。使えるコインの額面が$c_1, c_2,..., c_m$と決まっているので

硬貨$c_1, c_2,..., c_m$を使った際にちょうど$n$円となる金額($n-c_1, n-c_2,..., n-c_m$)

ですね。$4$問目風に言い換えると「最後に追加したコインの金額」でしょうか。$4$問目は$2$種類でしたが今回は$m$種類ということですね。求めたいものは$n$円払うのに使用するコインの枚数の最小値なので、追加する情報としては

$n-c_1, n-c_2,..., n-c_m$円支払った時点で使用したコインの枚数の最小値

が欲しいです。さて、欲しい情報が配列チックなのでdpは2次元とします。$i$, $j$, $dp[i][j]$を何に設定するかですが、これは$4$問目と同じ感じで$i$をコインの種類、$j$を金額、$dp[i][j]$をコイン$c_1, c_2,..., c_i$を使って$j$円を払うときに使用するコインの枚数の最小値としましょう。

これまでの考えをもとに式を立てます。定数は$j=0$でコインの枚数が$0$である場合とコイン$c_1=1$のみを使用する場合($i=0$)で金額$j$に対してコインの枚数が$j$枚となる場合です。

その他の場合は$i-1$までのコインを使って$j$円支払う場合の枚数と$i$までのコインを使って$j$円を支払う場合の枚数を比べて、枚数の少ない方を取って行けばよいです。

$i$までのコインを使う場合の使用枚数は$j$が金額なので$dp[i][j-c_i]$の枚数に$1$足すことで得られます。

$$
\begin{equation*}
dp[i][j] = \left \{ \begin{array}{lll} 0 & (j=0) \\ j & (i=0) \\ min(dp[i-1][j], dp[i][j-c_i]+1) & (i \geq 1) \\ \end{array} \right. \end{equation*}
$$

後は実装するだけです。配列の範囲外アクセスには注意しましょう。

coin.cpp

#include <iostream>
#include <vector>
int main() {
    int n, m; std::cin >> n >> m;
    std::vector<int> c(n);
    for(auto& i: c) std::cin >> i;

    std::vector<std::vector<int>> dp(m, std::vector<int>(n + 1));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n + 1; ++j) {
            if(j == 0)
                dp.at(i).at(j) = 0;
            else if(i == 0)
                dp.at(i).at(j) = j;
            else if(j - c.at(i) < 0)
                dp.at(i).at(j) = dp.at(i - 1).at(j);
            else
                dp.at(i).at(j) = std::min(dp.at(i - 1).at(j), dp.at(i).at(j - c.at(i)) + 1);
        }
    }
    std::cout << dp.at(m - 1).at(n) << std::endl;
    return 0;
}

6問目 Knapsack 1

実行時間制限($2\sec$)

$N$個の品物があります。品物には$1,2,…,N$と番号が振られています。各$i (1≤i≤N)$について、品物$i$の重さは$w_i$で、価値は$v_i$です。

太郎君は、$N$個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量は$W$であり、持ち帰る品物の重さの総和は$W$以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

品物をコイン、総重量を金額と考えるとまんまコイン問題と同じ気がするので、$i$を品物、$j$を総重量、$dp[i][j]$を(今回求めるものが価値の総和なので)$i$番目までの品物を重さ$j$以下になるように選んだ時の価値の総和の最大値として直接式が立てられそうな気がしますね。

定数は総重量$0$で品物を持たない場合と、品物を$1$つだけナップサックに入れる場合とすれば次のようになります

$$
\begin{equation*}
dp[i][j] = \left \{ \begin{array}{ll} 0 & (j=0) \\ v_i & (j \geq w_i) \\ \end{array} \right. \end{equation*}
$$

その他の場合は荷物を追加しない($i-1$の状態を引き継ぐ)場合と荷物を追加する場合を比べてその最大値を取ればよいので、次のようになります。コイン問題とは異なり、同じ荷物を何度も追加することはできないので$dp[i][j-w_i]$でなく$dp[i-1][j-w_i]$からそれまでの総価値を取ってくる必要があることに注意します。

$$
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w_i] + v_i)
$$

あとはこれを実装すればよいです。初期化を$dp[0][0]$だけで済ますことができないので初期化パートと問題を解くパートでわかれています。最大値が32bitに収まらない場合があること、配列外へのアクセスに注意します。

knapsack1.cpp

#include <iostream>
#include <vector>
struct Goods{ int w, v; };
int main() {
    int n, w; std::cin >> n >> w;
    std::vector<Goods> goods(n);
    for(auto& i: goods) std::cin >> i.w >> i.v;

    std::vector<std::vector<long long int>> dp(n, std::vector<long long int>(w + 1, 0));
    for(int i = 0; i < n; ++i) {
        const auto [wi, vi] = goods.at(i);
        for(int j = 0; j < w + 1; ++j) {
            if(j >= wi)
                dp.at(i).at(j) = vi;
        }
    }
    for(int i = 0; i < n; ++i) {
        const auto [wi, vi] = goods.at(i);
        for(int j = 0; j < w + 1; ++j) {
            if(i >= 1 && j - wi >= 0)
                dp.at(i).at(j) = std::max(dp.at(i - 1).at(j), dp.at(i - 1).at(j - wi) + vi);
            else if(i >= 1)
                dp.at(i).at(j) = dp.at(i - 1).at(j);
        }
    }
    std::cout << dp.at(n-1).at(w) << std::endl;
    return 0;
}

7問目 Knapsack 2

実行時間制限($2\sec$)

$N$個の品物があります。品物には$1,2,…,N$と番号が振られています。各$i (1≤i≤N)$について、品物$i$の重さは$w_i$で、価値は$v_i$です。

太郎君は、$N$個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量は$W$であり、持ち帰る品物の重さの総和は$W$以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

$6$問目と同じですが、制約が異なります。

D - Knapsack 1	E - Knapsack 2
$$1 \leq N \leq 100 \\ 1 \leq W \leq 10^5 \\ 1 \leq w_i \leq W \\ 1 \leq v_i \leq 10^9$$	$$1 \leq N \leq 100 \\ 1 \leq W \leq 10^9 \\ 1 \leq w_i \leq W \\ 1 \leq v_i \leq 10^3$$

先ほどと同じように解くことはできないので、何とかKnapsack 2で緩和された$v_i$の条件を使えないかを考えると、価値の総和の最大値がどんなに大きくなっても$100 \times 10^3 = 10^5$なので、これを$j$の要素として設定してみることを考えます。

$i$は品物、$j$は価値の総和、$dp[i][j]$を$i$番目までの品物をその総価値が$j$になるように選んだ場合の重量の総和の最小値とするわけです。

定数は先ほどと同様に$j=0$で総重量が$0$である場合と、品物$1$つだけをナップサックに入れる場合とすると、次のようになります。

$$
\begin{equation*}
dp[i][j] = \left \{ \begin{array}{ll} 0 & (j=0) \\ w_i & (j = v_i) \\ \end{array} \right. \end{equation*}
$$

そのほかの場合は$i$までの品物を追加した場合について重量の最小値を記録していきます。完成した式自体は$6$問目と大差はありませんね。

$$
dp[i][j]=min(dp[i-1][j], dp[i-1][j-v_i]+w_i)
$$

以上をそのまま実装すればACとなります。dpに記録しているのは問題の直接的な答えではなく荷物の総重量なので、答えを別の変数で記録する必要があることと、オーバーフロー、配列の範囲外へのアクセスに注意します。

knapsack2.cpp

#include <iostream>
#include <vector>
const int v = 100 * 1000 + 1;
struct Goods{ int w, v; };
int main() {
    int n, w; std::cin >> n >> w;
    std::vector<Goods> goods(n);
    for(auto& i: goods) std::cin >> i.w >> i.v;

    std::vector<std::vector<long long int>> dp(n, std::vector<long long int>(v, INT32_MAX));
    int max = INT32_MIN;
    for(int i = 0; i < n; ++i) {
        const auto [wi, vi] = goods.at(i);
        for(int j = 0; j < v; ++j) {
            if(j == 0)
                dp.at(i).at(j) = 0;
            if(j == vi)
                dp.at(i).at(j) = wi;
        }
    }
    for(int i = 0; i < n; ++i) {
        const auto [wi, vi] = goods.at(i);
        for(int j = 0; j < v; ++j) {
            if(i >= 1 && j - vi >= 0)
                dp.at(i).at(j) = std::min(dp.at(i - 1).at(j), dp.at(i - 1).at(j - vi) + wi);
            else if(i >= 1)
                dp.at(i).at(j) = dp.at(i - 1).at(j);
            
            if(dp.at(i).at(j) <= w)
                max = std::max(max, j);
        }
    }
    std::cout << max << std::endl;
    return 0;
}

dp(n, std::vector<long long int>(v, INT32_MAX));の初期値をINT64_MAXではなくINT32_MAXとしているのはdp.at(i - 1).at(j - vi) + wiでオーバーフローが発生してしまうからです。オーバーフローが発生し、$dp[N-1][V] \leq W$となった場合、答えが常に$V$になってしまいます。

初期値の状態から何かを足す処理をする場合は初期値をINTMAXにするのではなく、それより小さいかつ結果が変わらない程度の値を入れておいた方が良さそうなことが分かります。

8問目最長共通部分列

実行時間制限($1\sec$)

最長共通部分列問題 (Longest Common Subsequence problem: LCS)は、２つの与えられた列$X={x_1,x_2,...,x_m}$と$Y={y_1,y_2,...,y_n}$の最長共通部分列を求める問題です。

ある列$Z$が$X$と$Y$の部分列であるとき、$Z$を$X$と$Y$の共通部分列と言います。例えば$X = {a, b, c, b, d, a, b}, Y = {b, d, c, a, b, a}$とすると、列${b, c, a}$は$X$と$Y$の共通部分列です。一方、列${b, c, a}$は$X$と$Y$の最長共通部分列ではありません。なぜなら、その長さは３であり、長さ４の共通部分列${b,c,b,a}$が存在するからです。長さが 5 以上の共通部分列が存在しないので、列${b,c,b,a}$は$X$と$Y$の最長共通部分列の１つです。

与えられた２つの文字列$X$、$Y$に対して、最長共通部分列$Z$の長さを出力するプログラムを作成してください。与えられる文字列は英文字のみで構成されています。

この問題においての最後の状態を$x_m$, $y_n$文字目まで読んだ状態とするとその直前の状態は

$x_{m-1},y_{n-1}$文字目まで読んだ状態
$x_m,y_{n-1}$文字目まで読んだ状態
$x_{m-1},y_n$文字目まで読んだ状態

です。ここで例えば

$x_{m-1},y_{n-1}$まで文字を読んだ時の最長共通部分列の長さ$(X_{m-1}Y_{n-1})_{LCS}$

が分かっていたとすると、

$x_m = y_n$の時$(X_mY_n)_{LCS}=(X_{m-1}Y_{n-1})_{LCS}+1$

と求めることができ、また、

$(X_{m}Y_{n-1})_{LCS}$及び$(X_{m-1}Y_{n})_{LCS}$

が分かっていたとすると、$(X_mY_n)_{LCS}$はこのどちらか大きい方を取ってくればよいので

$x_m \neq y_n$の時$(X_mY_n)_{LCS} = max((X_{m-1}Y_n)_{LCS}, (X_mY_{n-1})_{LCS})$

であると分かります。
定数は$X, Y$どちらかが一文字も読んでいない状態で$(X_0Y_j)_{LCS}=0$, $(X_iY_0)_{LCS}=0$です。これを式にまとめると

$$
\begin{equation*}
(X_iY_j)_{LCS} = \left \{ \begin{array}{lll} 0 & (i=0 \lor j=0) \\ (X_{i-1}Y_{j-1})_{LCS}+1 & (x_i = y_j) \\ max((X_{i-1}Y_j)_{LCS}, (X_iY_{j-1})_{LCS}) & (x_i \neq y_j) \\ \end{array} \right. \end{equation*}
$$

これをそのまま実装すればよいです。読んでない状態は文字列の先頭に空文字列を入れることで表現します。

#include <iostream>
#include <vector>
#include <string>
int LCS(std::string x, std::string y) {
    x = " " + x;
    y = " " + y;
    int m = x.length();
    int n = y.length();
    std::vector<std::vector<int>> lcs(m, std::vector<int>(n));

    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            if(i == 0 || j == 0)
                lcs.at(i).at(j) = 0;
            else if(x.at(i) == y.at(j))
                lcs.at(i).at(j) = lcs.at(i - 1).at(j - 1) + 1;
            else
                lcs.at(i).at(j) = std::max(lcs.at(i - 1).at(j), lcs.at(i).at(j - 1));
        }
    }
    return lcs.at(m - 1).at(n - 1);
}
int main() {
    int q; std::cin >> q;
    for(int i = 0; i < q; ++i) {
        std::string x, y; std::cin >> x >> y;
        std::cout << LCS(x, y) << std::endl;
    }
    return 0;
}

DP まとめコンテストにあるほぼ同じ問題のLCSでは文字列の長さではなく該当の文字列を答えるように指定されています。文字列を答えるならlcsの中身をstd::stringにするだけでいいのではないかと思うんですが、(多分)文字列のコピーのコストが無視できない位嵩んでTLEになってしまうので、文字列の長さを求めた過程から実際の文字列を復元するという方法を取ります。

具体的には、現在地$lcs[i][j]$と現在地までのルートであり得るもの($lcs[i-1][j-1]$, $lcs[i-1][j]$, $lcs[i][j-1]$)を比べて、どこからやってきたのかを特定していきます。DPの漸化式が

$$
\begin{equation*}
(X_iY_j)_{LCS} = \left \{ \begin{array}{lll} 0 & (i=0 \lor j=0) \\ (X_{i-1}Y_{j-1})_{LCS}+1 & (x_i = y_j) \\ max((X_{i-1}Y_j)_{LCS}, (X_iY_{j-1})_{LCS}) & (x_i \neq y_j) \\ \end{array} \right. \end{equation*}
$$

なので、$lcs[i][j]$が$lcs[i-1][j]$もしくは$lcs[i][j-1]$と同値なら$x_i \neq y_j$で遷移してきてて、それ以外では$x_i = y_j$だったと分かるので、これをもとに文字列を構築するとACを得られます。

9問目最大正方形

実行時間制限($1\sec$)

一辺が$1$cm のタイルが、$H \times W$個並べられています。タイルは汚れているもの、綺麗なもののいずれかです。

綺麗なタイルのみを使ってできる正方形の面積の最大値を求めてください。

左上タイルを$(1,1)$タイル、右下のタイルを$(H, W)$タイルとすると、最後の状態は$(H, W)$タイルを読んだ状態で、その直前は

$(H-1, W-1)$, $(H-1, W)$, $(H, W-1)$タイルを読んだ状態

となりますが、今回の場合はたとえ$(H-1, W-1)$タイルまでを使ってできる正方形の面積の最大値が分かっていたとしても$(H, W)$タイルまでを使ってできる正方形の面積の最大値は全く持って分からないです。なんならこの情報だけでは毎回そのタイルを含む正方形を探さなくてはいけなくなってしまっています。

そこで、直接答えを求められなくても良いので、間接的に面積の最大値を求められるような情報を探してみると、少なくとも現在地の左上のタイルを使って正方形が作れるかどうかは知っていないと現在地で正方形が作れるかなんてわからないので

$(H-1, W-1)$までのタイルを使って、$(H-1, W-1)$タイルが右下に来る正方形を作った場合の一辺の長さの最大値

があればそこそこ都合がよさそうなことに気が付きます。例えば以下のようなタイルがあったとします。(xが汚れたタイル、.が綺麗なタイルです。)

. . x
. . .
. . .

このタイルに対して、左上から右下に向かって上に挙げた値($(i, j)$タイルを右下に置いたときに作れる正方形の一辺の長さの最大値)を入れていくと

1 1 x
1 2 1
1 2 2

となります。

ここで、$(i-1, j-1)$を右下に含む正方形を作るときにできる一辺の長さの最大値が分かっているので$(i, j)$タイルの上側と左側を調べて汚れたタイルが無ければ$(i, j)$で作れる正方形の一辺の長さの最大値を求めることができると分かります。

つまり、上側に$1$マス、左側に$2$マスの余裕があるとして、左上のタイルを右下に置いたときに作れる正方形の一辺の長さの最大値が$1$なら現在地では$2 \times 2$の正方形を作れるということなので、上側と左側に余裕がどれだけあるかが分かれば現在地(o)の正方形の大きさの最大値は求まるわけです。

x . x | x . x | x . x
x # . | x 1 . | x # #
. . . | . . o | . # #

上側と左側にどれだけ余裕があるかを1マスずつ調べていくのは効率が悪いので、周りに使えそうな情報が無いかを考えると、$(i-1, j)$, $(i, j-1)$タイルを右下に含む正方形を作るときの一辺の長さの最大値が使えそうであると分かります。

従って、$(i,
j)$を右下のタイルとする正方形の一辺の長さの最大値を$E_{i, j}$とすると次のように考えることができます。

$$
\begin{equation*}
E_{i, j} = \left \{ \begin{array}{ll} E_{i-1, j-1}+1 & (E_{i-1, j}, E_{i, j-1} \geq E_{i-1, j-1}) \\ min(E_{i-1, j}, E_{i, j-1})+1 & (E_{i-1, j}, E_{i, j-1} < E_{i-1, j-1}) \\ \end{array} \right. \end{equation*}
$$

上の式は現在地の左上のタイルを使って正方形を作った場合の一辺の長さが、上と左のタイルのそれよりも短いならば、現在地では一辺が$E_{i-1, j-1}+1$の正方形を作れると言っています。

例えば、$(2, 2)$タイルでは左上のタイルから$1 \times 1$, 左のタイルから$1 \times 1$, 上のタイルから$1 \times 1$の正方形が作れるので、$(2, 2)$タイルから一辺$E_{1, 1}+1$の正方形を作れることが分かります。

# . x | . . x | . # x | # # x
. o . | # o . | . o . | # # .
. . . | . . . | . . . | . . .

下の式はその反対で、例えば$(3, 3)$タイルでは左上のタイルからは$2 \times 2$, 左のタイルからは$2 \times 2$の正方形が作れますが、上のタイルからは$1 \times 1$の正方形しか作ることはできないので、$(3, 3)$タイルからは一辺$min(E_{2, 3}, E_{3, 2})+1=2$の正方形を作ることしかできないということです。

# # x | . . x | . . x | . . x
# # . | # # . | . . # | . # #
. . o | # # o | . . o | . # #

初期値はタイルが汚れていなければ$1$, 汚れていれば$0$です。このまま実装すればACとなります。eul, eu, elは$E$ upper left, $E$ upper, $E$ leftのつもりです。

largest_square.cpp

#include <iostream>
#include <vector>
int main() {
    int h, w; std::cin >> h >> w;
    std::vector<std::vector<int>> tile(h, std::vector<int>(w));
    int max = INT32_MIN;
    for(auto& i: tile) {
        for(auto& j: i) {
            int t; std::cin >> t;
            j = t == 1 ? 0 : 1;
            max = std::max(j, max);
        }
    }
    for(int i = 1; i < h; ++i) {
        for(int j = 1; j < w; ++j) {
            if(tile.at(i).at(j) == 0) continue;
            int eul = tile.at(i - 1).at(j - 1), eu = tile.at(i - 1).at(j), el = tile.at(i).at(j - 1);

            if(eul <= eu && eul <= el)
                tile.at(i).at(j) = eul + 1;
            else
                tile.at(i).at(j) = std::min(eu, el) + 1;
            max = std::max(tile.at(i).at(j), max);
        }
    }
    std::cout << max * max << std::endl;
    return 0;
}

10問目連鎖行列積

実行時間制限($1\sec$)

$n$個の行列の連鎖$M_1,M_2,M_3,...,M_n$が与えられたとき、スカラー乗算の回数が最小になるように積$M_1M_2M_3...M_n$の計算順序を決定する問題を連鎖行列積問題(Matrix-Chain Multiplication problem)と言います。

$n$個の行列について、行列$M_i$の次元が与えられたとき、積$M_1M_2...M_n$の計算に必要なスカラー乗算の最小の回数を求めるプログラムを作成してください。

$a \times b$の行列$A$と$b \times c$の行列$B$の掛け算では$a \times b \times c$回の乗算が必要になり、計算の結果として$a \times c$の行列$C$が得られます。つまり、$M_i$の行数を$i_r$, 列数を$i_c$とするとこの問題は

連続する二つの行列$M_{i-1}(i-1_r \times i-1_c)$と$M_i(i_r \times i_c)$の積を取り、$M_{i-1, i}(i-1_r \times i_c)$とするときに$i-1_r \times i_r \times i_c$のコストを支払う。$M_1M_2M_3...M_n$が$M_{1, 2, 3, ..., n}$となったときに支払うコストの総和の最小値を求めよ。

と書き換えることができます。ここで、最後の状態は$M_{1, 2, 3,...,n}$が求まった状態で、その直前の状態は

$M_{1,...,i} \times M_{i+1,...,n}$

です。$i$の適切な決め方は置いといて、この掛け算を行った上で$M_{1,2,3,...,n}$を求めるために必要な乗算の回数の最小値$min_{1,...,n}$を求めるためには

$min_{1, ..., i}$及び$min_{i+1,...,n}$

が必要です。これが分かっていれば$min_{1,...,n}=min_{1,...,i} + min_{i+1,...,n}+ (1_r \times i+1_r \times n_c)$と求めることができます。

というわけで$min_{i,...,j}$の求め方を考えます。例えば$M_1M_2M_3$では、$M_1M_2$と$M_2M_3$のコストが分かっている場合$M_i,...,M_j$のコストを$cost_{i,...,j}$とすれば

$min_{1,2,3}=min(cost_{1,2}+1_r \times 3_r \times 3_c, cost_{2,3}+1_r \times 2_r \times 3_c)$

です。また、$M_1M_2M_3M_4$では

$min_{1,2,3,4}=min($
- $cost_{1,2,3}+1_r \times 4_r \times 4_c,$
- $cost_{1,2}+cost_{3,4}+1_r \times 3_r \times 4_c,$
- $cost_{2,3,4}+1_r \times 2_r \times 4_c$
  $)$

となります。このように、行列積を計算する際の乗算の回数は元の行列を計算するときのコストだけでなく、その行列の形にも影響されるため考えうるすべてのパターンを調べる必要があることが分かります。$dp[i][j]=min_{i,...,j}$になるように式を立てると次のようになります。

$$
\begin{equation*}
dp[i][j] = \left \{ \begin{array}{ll} 0 & (i=j) \\ min(cost_{i,...,k}+cost_{k+1,...,j}+i_r \times k+1_r \times j_c) & (i \leq k < j) \\ \end{array} \right. \end{equation*}
$$

$min$は$i, j$間を全て回した結果を取ります。さて、ここまで来たらそのまま実装してしまいたくなりますが、実装方法には少し注意する必要があります。

このまま実装すればいいんじゃないの？

#include <iostream>
#include <vector>
struct Matrix { int r, c; };
int main() {
    int n; std::cin >> n;
    std::vector<Matrix> m(n);
    for(auto& i: m) std::cin >> i.r >> i.c;

    std::vector<std::vector<long long>> dp(n, std::vector<long long>(n));
    for(int i = 0; i < n; ++i) {
        for(int j = i; j < n; ++j) {
            if(i == j) {
                dp.at(i).at(j) = 0;
                continue;
            }
            long long min = INT32_MAX;
            for(int k = i; k < j; ++k) {
                min = std::min(dp.at(i).at(k) + dp.at(k + 1).at(j) + (m.at(i).r * m.at(k + 1).r * m.at(j).c), min);
            }
            dp.at(i).at(j) = min;
        }
    }
    std::cout << dp.at(0).at(n - 1) << std::endl;
    return 0;
}

と思ってしまいますが、よく見ると$i$のループ一週目で$dp[0][n-1]$が書き換えられると、それ以降の結果がどうなっていようが、$dp[0][n-1]$の結果が更新されないといった状況に陥ります。なぜこんなことになってしまっているのかというと、初めから行列積を求めるときに使う行列の数を$n$個までOKとしてしまっているからです。

$dp[0][n-1]$にたどり着いて、そこで全パターンの行列積の回数を求めたところで、そもそも$dp[2][n-1]$だとか$dp[3][n-1]$がまだ求まっていないので、正確な値が分からなくなってしまうわけです。

ということで使う行列の数を$2$から$n$まで増やしつつ$i, j$を回すという方法を取ります。つまり$j$の値を行列の数を$c+1$として$j=i+c$とすることで、行列の数を制限します。

これをこのまま実装してしまえばACとなります。

matrix_chain_multiplication.cpp

#include <iostream>
#include <vector>
struct Matrix { int r, c; };
int main() {
    int n; std::cin >> n;
    std::vector<Matrix> m(n);
    for(auto& i: m) std::cin >> i.r >> i.c;

    std::vector<std::vector<long long>> dp(n, std::vector<long long>(n));
    for(int c = 0; c < n; ++c) {
        for(int i = 0; i + c < n; ++i) {
            int j = i + c;
            if(i == j) {
                dp.at(i).at(j) = 0;
                continue;
            }
            long long int min = INT64_MAX;
            for(int k = i; k < j; ++k)
                min = std::min(
                    dp.at(i).at(k) + dp.at(k + 1).at(j) + (m.at(i).r * m.at(k + 1).r * m.at(j).c), 
                    min
                );
            dp.at(i).at(j) = min;
        }
    }
    std::cout << dp.at(0).at(n - 1) << std::endl;
    return 0;
}

おわりに

DPを使うと分かった上で問題解いても難しかった...特にVacation以降全部。

なるべくDPで使う配列の次元だとかを一撃で出さないように理由付けしてますが、配列の次元をどうするかだったり、答えを求めるためには何重のループが必要かだったりを1から考えて出すのはやっぱり難しいので、DPを初めて勉強して問題に挑戦して全く歯が立たなくても気にすることはないと思います。

一応言っておきますが、今回は全ての問題を同じようなアプローチで解くことができていましたが、もしかしたらこれはたまたまこの10問がこの方法で解けただけかもしれません。というのも、冒頭でも書いた通り私もDPについては初心者なのでこの10問以外を解いたことがありません。

ということで、最後の一歩手前の状況を見て、そこから欲しい情報を探すという方法は問題を解くときの一つの指針として考えておくとよいかもしれないです。

参考