C++で奇妙なコイン投げ問題を解く方法（動的計画法）

この記事では、確率を扱う興味深いアルゴリズム問題「奇妙なコインの投げ方」をC++で解く方法を解説します。動的計画法（DP）を使った効率的な解法を見ていきましょう。

問題の概要

いくつかのコインがあり、i番目のコインは投げたときに表が出る確率が prob[i] であるとします。すべてのコインをちょうど1回ずつ投げたとき、表が target 枚になる確率を求めてください。

例えば、prob 配列が [0.5, 0.5, 0.5, 0.5, 0.5] で target が 0 の場合、出力は 0.03125 となります。これは、5枚すべて裏になる確率 (0.5)^5 を意味しています。

解法のアプローチ

この問題は動的計画法で解くことができます。dp[i][j] を「最初の i+1 枚のコインの中から j 枚が表になる確率」と定義します。各コインについて「表になる」か「裏になる」かの2つの状態を考慮しながら漸化式を立てていきます。

手順

• n := prob 配列のサイズとする
• サイズ n × (target + 5) の2次元配列 dp を作成する
• 初期値として dp[0,0] = 1 – prob[0]、dp[0,1] = prob[0] を設定する（0番目のコインが裏・表になるそれぞれの確率）
• i = 1 から n – 1 まで繰り返す：
  • dp[i, 0] := (1 – prob[i]) * dp[i – 1, 0]（新しいコインが裏の場合）
  • j = 1 から min(i + 1, target) まで繰り返す：
    • dp[i, j] := (1 – prob[i]) * dp[i – 1, j] + prob[i] * dp[i – 1, j – 1]
• 最後に dp[n – 1, target] を返す

ここで重要なのは漸化式の考え方です。j 枚が表になるには、次の2通りがあります。

• i番目のコインが裏で、それまでに j 枚表だった → (1 – prob[i]) * dp[i – 1, j]
• i番目のコインが表で、それまでに j – 1 枚表だった → prob[i] * dp[i – 1, j – 1]

この2つの確率を足し合わせることで、現在の状態の確率が求まります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   double probabilityOfHeads(vector<double>& prob, int target) {
      int n = prob.size();
      vector < vector <double> > dp(n, vector <double>(target+5));
      dp[0][0] = 1- prob[0];
      dp[0][1] = prob[0];
      for(int i =1;i<n;i++){
         dp[i][0] = (1-prob[i])*dp[i-1][0];
         for(int j =1;j<=min(i+1,target);j++){
            dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1];
         }
      }
      return dp[n-1][target];
   }
};
main(){
   vector<double> v = {0.5,0.5,0.5,0.5,0.5};
   Solution ob;
   cout << (ob.probabilityOfHeads(v, 0));
}

入力例

[0.5,0.5,0.5,0.5,0.5]
0

出力例

0.03125

計算量の分析

• 時間計算量： O(n × target) — 各コインについて最大 target 回までの遷移を行うためです。
• 空間計算量： O(n × target) — 2次元DPテーブルが必要になります。ただし、1次元配列を使った工夫により空間を削減することも可能です。

このように、動的計画法を使えば全組み合わせ（2^n 通り）を列挙せずとも効率的に答えを求められます。確率系のDPは「各選択肢ごとの確率を加算していく」という点が特徴なので、他の類似問題にも応用できる考え方です。