C++で点NからN回移動した後にすべての点へ到達する確率を求める方法

問題概要

数直線上の初期位置を表す整数Nと、左方向へ移動する確率Lが与えられます。点Nを出発してN回の移動を完了したとき、数直線上の各点に到達する確率をすべて求めます。なお、1回の移動ごとに、必ず左または右のどちらかに1だけ進むものとします。

例えば、入力が n = 2、l = 0.5 の場合、出力は [0.25, 0, 0.5, 0, 0.25] となります。これは、2回の移動後に位置0・2・4へそれぞれ到達する確率を表しています。

解法のアプローチ

この問題は動的計画法(DP)を使うことで効率的に解けます。「i回目の移動後に位置jにいる確率」を二次元配列A[i][j]に格納しながら、段階的に確率を伝播させていきます。

具体的な手順は以下の通りです。

1. 右へ移動する確率 high を「1 − low」として計算します。
2. サイズ (n+1) × (2n+1) の二次元配列Aを定義し、すべての要素を0で初期化します。
3. 1回目の移動後の状態として、A[1][n+1] = high(右へ移動した場合)、A[1][n−1] = low(左へ移動した場合)を設定します。
4. i = 2 から n まで、次の処理を繰り返します。
   • j = 1 から 2n まで昇順に:A[i][j] += A[i−1][j−1] × high(ひとつ左の位置から右へ移動してくるケース)
   • j = 2n−1 から 0 まで降順に:A[i][j] += A[i−1][j+1] × low(ひとつ右の位置から左へ移動してくるケース)
5. 最後に A[n][i](i = 0 から 2n)を順番に出力します。

ここで、出力のインデックスiは数直線上の位置そのものに対応しており、N回の移動後に到達しうる範囲は位置0から2Nまでになります。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void find_prob(int n, double low) {
    double high = 1 - low;
    double A[n + 1][2 * n + 1] = {{0}};
    A[1][n + 1] = high;
    A[1][n - 1] = low;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 2 * n; j++)
            A[i][j] += (A[i - 1][j - 1] * high);
        for (int j = 2 * n - 1; j >= 0; j--)
            A[i][j] += (A[i - 1][j + 1] * low);
    }
    for (int i = 0; i < 2*n+1; i++)
        cout << A[n][i] << endl;
}
int main() {
    int n = 2;
    double low = 0.6;
    find_prob(n, low);
}

入力

2, 0.6

出力

0.36
0
0.48
0
0.16

出力結果の解釈

この結果は、左へ移動する確率が0.6の場合、2回の移動後に次のような分布になることを示しています。

• 位置0へ到達する確率:0.36(左→左 = 0.6 × 0.6)
• 位置2へ到達する確率:0.48(左→右 または 右→左 = 0.6 × 0.4 + 0.4 × 0.6)
• 位置4へ到達する確率:0.16(右→右 = 0.4 × 0.4)

位置1と3には偶数回の移動では到達できないため、確率は0になります。このようにDPを使えば、各ステップの確率を累積していくだけで、すべての到達点の確率をO(N²)の計算量で求められます。