AtcoderのEducational DP Contestの問題 I - Coins を動的計画で解いた場合とメモ化再帰で解いた場合の実行時間の違いについて

Question

実現したいこと

• ある問題を動的計画で解いた場合とメモ化再帰で解いた場合とで、実行時間にどの程度差が生じるのか知りたい。

前提

私は動的計画法について勉強中で、atcoder内の以下の問題に取り組んでいます。
URL: https://atcoder.jp/contests/dp/tasks/dp_i

実行時間制限: 2 sec / メモリ制限: 1024 MB
**問題文**
N を正の奇数とします。
N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 
各 i (1≤i≤N) について、コイン i を投げると、確率 p_iで表が出て、確率 1−p_i で裏が出ます。
太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。

**制約**
- N は奇数である。
- 1 ≤ N ≤ 2999
- p_i は実数であり、小数第 2 位まで与えられる。
- 0 < p_i <1

**入力**
入力は以下の形式で標準入力から与えられる。
N
p_1
​p_2
… 
p_N
​
**出力**
表の個数が裏の個数を上回る確率を出力せよ。 絶対誤差が 10^(−9) 以下ならば正解となる。

質問

この問題を動的計画とメモ化再帰で解く2つのプログラムをそれぞれ作成したのですが、動的計画では任意の入力に対して100 msec以内で終了するのに対して、メモ化再帰の場合は制限時間の2 sec を超過してしまいます。

動的計画とメモ化再帰の違いに関して、

• ボトムアップかトップダウンどちらで最終的な解答を得ようとするかの違いはあるものの、内部の計算は似たもの
• メモ化再帰では関数を繰り返し呼び出すことによるオーバヘッドが生じるため、動的計画よりは遅くなる可能性がある

と理解しているのですが、それだけで実行時間にここまで大きな差が生まれるものなのでしょうか？
それとも、私のメモ化再帰の実装が悪いために遅くなってしまっているのでしょうか？

ぜひ、教えていただければ幸いです。

動的計画にもとづくプログラム

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    int N;
    std::cin >> N;
    std::vector<double> p(N, 0.0);
    for (int i = 0; i < N; i++) {
        std::cin >> p[i];
    }

    std::vector<std::vector<double>> dp(N + 1, std::vector<double>(N + 1, 0.0));
    dp[0][0] = 1.0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }

    double res = 0.0;
    for (int i = N / 2 + 1; i <= N; i++) {
        res += dp[N][i];
    }

    std::cout << std::fixed << std::setprecision(10) << res << std::endl;

    return 0;
}

メモ化再帰にもとづくプログラム

#include <iomanip>
#include <iostream>
#include <vector>

int N;
std::vector<double> p(10000, 0.0);
std::vector<std::vector<double>> dp(10000, std::vector<double>(10000, 0.0));

double rec(int i, int j) {
    if (dp[i][j] != 0.0) {
        return dp[i][j];
    }
    if (i == 0 and j == 0) {
        return 1.0;
    }
    if (i < j) {
        return 0.0;
    }
    if (i > 0 and j == 0) {
        return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]);
    }
    return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1];
}

int main() {
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> p[i];
    }

    double result = 0.0;
    for (int j = N / 2 + 1; j <= N; j++) {
        result += rec(N, j);
    }

    std::cout << std::fixed << std::setprecision(10) << result << std::endl;

    return 0;
}

Answer 1

計算済みかをif (dp[i][j] != 0.0)で判定しているのが間違いです。
この判定だと、計算結果が0.0になった場合と区別ができません。

例えば、入力として、N=2999、p1～pN=0.5 を与えた場合、dp[2999][2507]あたりでdoubleで表現できる限界を下回り、計算結果が0.0と等しくなってしまいます。そうなると、計算済みなのに未計算とみなされ、毎回計算が行われてしまいます。

計算済みかの判定は、計算結果として表れることが絶対にない数字で行うようにしましょう。今回なら、マイナスの確率はありえないので、初期値に-1.0を入れておいて、マイナスだったら未計算と判定するなど。

#include <iomanip>
#include <iostream>
#include <vector>

int N;
std::vector<double> p(10000, 0.0);
std::vector<std::vector<double>> dp(10000, std::vector<double>(10000, -1.0));

double rec(int i, int j) {
    if (dp[i][j] >= 0.0) {
        return dp[i][j];
    }
    if (i == 0 and j == 0) {
        return 1.0;
    }
    if (i < j) {
        return 0.0;
    }
    if (i > 0 and j == 0) {
        return dp[i][j] = rec(i - 1, j) * (1.0 - p[i - 1]);
    }
    return dp[i][j] = rec(i - 1, j) * (1.0 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1];
}

int main() {
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> p[i];
    }

    double result = 0.0;
    for (int j = N / 2 + 1; j <= N; j++) {
        result += rec(N, j);
    }

    std::cout << std::fixed << std::setprecision(10) << result << std::endl;

    return 0;
}

Comments

[MONOSPEC]

回答ありがとうございます！
ご指摘の通りで、メモする計算結果が0.0に等しくなってしまう可能性があることを見落としていたようです。メモの初期値を-1.0とすることで解決しました。