DP入門：Educational DP Contest A・B

Pocket

▲「お兄ちゃん！　最近あたしと話してくれない気がするんだけど！」

■「え、そんなことないよ。今朝だって話したよね」

▲「そういうことじゃないの！　っていうか、ご無沙汰すぎてDP忘れちゃったんだけど！」

■「動的計画法？　だったら、少し前に Educational DP Contest という教育的なコンテストが開催されたみたいだよ」

▲「それももう “少し前” なのかわかんないけど……　まあいいや、その問題を教えて！」

■「うん、いいよ。でも、最初の方の問題なら自力で解けるんじゃないかな」

▲「じゃあやってみる！」

A – Flog1

■「A問題はこんな問題だね」

N 個の足場があります。足場には 1,2,…,N と番号が振られています。各 i (1≤i≤N) について、足場 i の高さは hi です。

最初、足場 1 にカエルがいます。カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

足場 i にいるとき、足場 i+1 または i+2 へジャンプする。このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

2≤N≤10^5

1≤hi≤10^4

▲「1つ右に行くか、2つ右に行くか選べるってことだね。それで、移動するときには高さの差だけコストがかかるんだよね」

■「愚直にやるとどうなる？」

▲「愚直って？」

■「計算量のことは気にせず、『あり得る全パターンを計算したら絶対解けるよね』みたいな発想で解くならどうなるかってこと」

▲「うーん、そもそも足場 N にたどり着く方法は何通りあるんだろう」

■「実は移動方法の数も有名な動的計画法の問題で、フィボナッチ数列になるんだけど、とりあえず多めに見積もってみよう」

▲「フィボナッチ数列？　そっちも気になるんだけど。適当に考えると、各足場で 1 つ右か 2 つ右か選べるんだから、2^N パターン？　絶対これより少ないけどね」

■「そんな感じだね。1 パターンについて総コストを計算するのに O(N) かかるから、ざっくり全体で O(N*2^N) だね」

▲「N ≤ 10^6 だから、間に合うわけないね」

■「こういう問題は、漸化式を立てると解けることが多いよ」

▲「漸化式っていうのは、数列 c[i] の値が分かれば、c[i+1] の値も分かる、みたいなやつだよね」

■「そうそう。今回の場合、 c[i] は何の値にするのが良いかな？」

▲「最後に知りたいのは “足場 N にたどり着くまでのコストの最小値” だから、こんな感じの値を設定すればいいんだよね。“c[i] = 足場 i にたどり着くまでのコストの最小値” とかどう？」

■「良いね。仮に c[0]〜c[i-1] が全部分かっているとして、そこから c[i] を計算する漸化式は作れる？」

▲「えっと、足場 i に来る直前は、足場 i-2 か足場 i-1 にいるんだよね。だから、そこまではコスト c[i-2] か c[i-1] でたどり着けるんだよね」

■「そうだね。逆に、それより少ないコストで足場 i-2 または i-1 には行けない」

▲「足場 i に行く方法は、足場 i-2 にコスト c[i-2] で移動してから足場 i に移動するか、足場 i-1 にコスト c[i-1] で移動してから足場 i に移動するかの 2 通りなんだよね」

■「うんうん」

▲「じゃあ、足場 i-2 に移動するのに必要なコストは、その少ない方だ！」

■「式で書くとどうなる？」

▲「こうかな？」

$$c[i] = \min(c[i-2] + |h[i-2] – h[i]|, c[i-1] + |h[i-1] – h[i]|)$$

■「その通り！　じゃあ実装してみようか」

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    vector<int> h(N);
    for (int i = 0; i < N; i++) {
        cin >> h[i];
    }
 
    // c[i] = 足場 i にたどり着くまでのコストの最小値
    vector<int> c(N, 0); // DP 配列の全要素を 0 で初期化
 
    // i = 1 からループ
    for (int i = 1; i < N; i++) {
        if (i == 1) {
            // i == 1 のときは i-1 からしか来られない
            c[i] = c[i - 1] + abs(h[i - 1] - h[i]);
        } else {
            c[i] = min(c[i - 2] + abs(h[i - 2] - h[i]),
                       c[i - 1] + abs(h[i - 1] - h[i]));
        }
    }
 
    cout << c[N - 1] << endl;
 
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main(void) {

int N;

cin >> N;

vector<int> h(N);

for (int i = 0; i < N; i++) {

cin >> h[i];

}

// c[i] = 足場 i にたどり着くまでのコストの最小値

vector<int> c(N, 0); // DP 配列の全要素を 0 で初期化

// i = 1 からループ

for (int i = 1; i < N; i++) {

if (i == 1) {

// i == 1 のときは i-1 からしか来られない

c[i] = c[i - 1] + abs(h[i - 1] - h[i]);

} else {

c[i] = min(c[i - 2] + abs(h[i - 2] - h[i]),

c[i - 1] + abs(h[i - 1] - h[i]));

}

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

return 0;

}

▲「これでどうだ！　……やった！　AC！」

■「良いね。今回の計算量は？」

▲「えっと、ループが 1 重だから O(N)？」

■「そうだね。ループの数を見るよにも、“状態の数” と ” 1 回の遷移の計算量” で考える方が良いかも」

▲「”状態の数” っていうのは、配列の添字のこと？」

■「うん。今回は一次元で N 要素だから O(N) だね」

▲「 1 回の遷移の計算量っていうのは、c[i] を計算するときのことだよね。今回は 2 つの min を取ってるだけだから O(1)？」

■「そう。だから掛け算して O(N) 。たまに単純な掛け算にならないものもあるけど、とりあえずはこういう考え方で良いと思うよ」

B – Frog2

▲「次の問題は……　あれ、A問題とほとんど同じだね」

N 個の足場があります。足場には 1,2,…,N と番号が振られています。各 ii (1≤i≤N) について、足場 i の高さは hi です。

最初、足場 1 にカエルがいます。カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

足場 ii にいるとき、足場 i+1,i+2,…,i+K のどれかへジャンプする。このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

$2 \leq N \leq 10^{5}$

$1 \leq K \leq 100$

$1 \leq h_{i} \leq 10^{4}$

■「そうだね。K に関する部分が変更点だね」

▲「さっきは 1 つ右か 2 つ右にしか行けなかったけど、今回は K 個右まで行けるんだね」

■「でもやることは変わらないね」

▲「c[i] の定義は同じで、足場 i にいる前の状態が i-K から i-1 まであり得るから、その K 通りで min を計算すればいいんだね」

$$c[i]=\min_{1\le k\le K}(c[i-k]+|h[i-k]-h[i]|)$$

■「飲み込みが早いね。さっきの場合は K=2 の場合だったってことだね」

▲「コードは、こんな感じかな？」

■「大きい値を無限大として定義するなら、1050000000 がオススメだよ」

#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1050000000
 
int main(void) {
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for (int i = 0; i < N; i++) {
        cin >> h[i];
    }
 
    // c[i] = 足場 i にたどり着くまでのコストの最小値
    vector<int> c(N, INF); // DP 配列の全要素をでっかい数で初期化
    c[0] = 0;              // c[0] が 0 であることは分かっている
 
    // i = 1 からループ
    for (int i = 1; i < N; i++) {
        // i-k が負にならないようにループ範囲の最大を min(i, K) に設定
        for (int k = 1; k <= min(i, K); k++) {
            c[i] = min(c[i], c[i - k] + abs(h[i - k] - h[i]));
        }
    }
 
    cout << c[N - 1] << endl;
 
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define INF 1050000000

int main(void) {

int N, K;

cin >> N >> K;

vector<int> h(N);

for (int i = 0; i < N; i++) {

cin >> h[i];

}

// c[i] = 足場 i にたどり着くまでのコストの最小値

vector<int> c(N, INF); // DP 配列の全要素をでっかい数で初期化

c[0] = 0; // c[0] が 0 であることは分かっている

// i = 1 からループ

for (int i = 1; i < N; i++) {

// i-k が負にならないようにループ範囲の最大を min(i, K) に設定

for (int k = 1; k <= min(i, K); k++) {

c[i] = min(c[i], c[i - k] + abs(h[i - k] - h[i]));

}

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

return 0;

}

▲「これで提出して……　AC！　やったね。ところで、なんで INF が 10億5000万なの？」

■「符号付き 32bit 整数で表せる数の最大値がだいたい 21億ちょっとだから。INF+INF が発生してもオーバーフローしないようにしたくて、でも MOD で使われる 10億7 よりは大きくしたいから、この値が良いかなと思う」

▲「ふーん、面倒なこと考えるんだね」

■「だいたいの問題で使える無限大を用意しておくと楽なんだよ。さて、今回の計算量は？」

▲「“状態の数” が O(N) で ” 1 回の遷移の計算量” が、これは O(K) ってことになるの？」

■「うん。K 通り計算して、その min を取っているから、O(K) だ」

▲「じゃあ、全体で O(NK) だね」

■「本番で問題を解くときはちゃんと実装前に計算量を考えておくんだよ」

▲「実装する前に考えるのって難しいよ」

■「 “状態の数” と ” 1 回の遷移の計算量” で考えるのに慣れれば大丈夫だよ」

▲「うーん、それができれば苦労しないってやつかなあ。このタイプのDPはなんとなく分かってきたっぽいから、もっと変なのやりたい！」

■「じゃあ、EDPC の後半で簡単そうなのをやってみようか」

▲「やってみよう！　また今度！」

■「今度かよ」

▲「今日はもう疲れたの！　じゃあ、また元号の変わった頃にお会いしましょ〜」

■「誰に向かって言ってるの！？」

Pocket