実現したいこと
- ある問題を動的計画で解いた場合とメモ化再帰で解いた場合とで、実行時間にどの程度差が生じるのか知りたい。
前提
私は動的計画法について勉強中で、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 を超過してしまいます。
動的計画とメモ化再帰の違いに関して、
- ボトムアップかトップダウンどちらで最終的な解答を得ようとするかの違いはあるものの、内部の計算は似たもの
- メモ化再帰では関数を繰り返し呼び出すことによるオーバヘッドが生じるため、動的計画よりは遅くなる可能性がある
と理解しているのですが、それだけで実行時間にここまで大きな差が生まれるものなのでしょうか?
それとも、私のメモ化再帰の実装が悪いために遅くなってしまっているのでしょうか?
ぜひ、教えていただければ幸いです。
動的計画にもとづくプログラム
C++
1#include <iomanip> 2#include <iostream> 3#include <vector> 4 5int main() { 6 int N; 7 std::cin >> N; 8 std::vector<double> p(N, 0.0); 9 for (int i = 0; i < N; i++) { 10 std::cin >> p[i]; 11 } 12 13 std::vector<std::vector<double>> dp(N + 1, std::vector<double>(N + 1, 0.0)); 14 dp[0][0] = 1.0; 15 for (int i = 0; i < N; i++) { 16 for (int j = 0; j <= i; j++) { 17 dp[i + 1][j] += dp[i][j] * (1.0 - p[i]); 18 dp[i + 1][j + 1] += dp[i][j] * p[i]; 19 } 20 } 21 22 double res = 0.0; 23 for (int i = N / 2 + 1; i <= N; i++) { 24 res += dp[N][i]; 25 } 26 27 std::cout << std::fixed << std::setprecision(10) << res << std::endl; 28 29 return 0; 30}
メモ化再帰にもとづくプログラム
C++
1#include <iomanip> 2#include <iostream> 3#include <vector> 4 5int N; 6std::vector<double> p(10000, 0.0); 7std::vector<std::vector<double>> dp(10000, std::vector<double>(10000, 0.0)); 8 9double rec(int i, int j) { 10 if (dp[i][j] != 0.0) { 11 return dp[i][j]; 12 } 13 if (i == 0 and j == 0) { 14 return 1.0; 15 } 16 if (i < j) { 17 return 0.0; 18 } 19 if (i > 0 and j == 0) { 20 return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]); 21 } 22 return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1]; 23} 24 25int main() { 26 std::cin >> N; 27 for (int i = 0; i < N; i++) { 28 std::cin >> p[i]; 29 } 30 31 double result = 0.0; 32 for (int j = N / 2 + 1; j <= N; j++) { 33 result += rec(N, j); 34 } 35 36 std::cout << std::fixed << std::setprecision(10) << result << std::endl; 37 38 return 0; 39}

回答1件
あなたの回答
tips
プレビュー
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。
2023/06/02 13:35