Pythonでポイントがn以下になる確率を求めるプログラムの実装方法

少し変わったルールのゲームを考えてみましょう。3つの整数 n、k、h が与えられます。ゲームは0ポイントからスタートし、各ターンごとに1からhまでの整数をランダムに1つ選び、その数だけポイントを獲得します。合計スコアがkポイント以上に達した時点でゲームは終了です。このとき、最終的なポイントがn以下になる確率を求めます。なお、どの数値も選ばれる確率はすべて等しいものとします。

たとえば、入力が n = 2、k = 2、h = 10 の場合、出力は 0.11 になります。

解き方のステップ

この問題は、現在のポイント数を状態とする再帰関数 dp() を使うことで効率的に解けます。手順は以下の通りです。

• 関数 dp() を定義します。引数には現在のポイント数 path を渡します。
  • path が k − 1 と等しい場合：
    min(n − k + 1, h) / h を返します。
  • path > n の場合：
    0 を返します。
  • path ≥ k の場合：
    1 を返します。
  • それ以外の場合：
    dp(path + 1) − (dp(path + h + 1) − dp(path + 1)) / h を返します。
• メイン側では、まず k が 0 かどうかを判定し、0 であれば 1 を返します。
• n < k の場合は、そもそも目標に届かないため 0 を返します。
• いずれにも該当しなければ、dp(0) を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, n, k, h):
        if not k: return 1
        if n < k: return 0
        def dp(path):
            if path == k - 1:
                return min((n - k + 1), h) / h
            if path > n:
                return 0
            if path >= k:
                return 1
            return dp(path + 1) - (dp(path + h + 1) - dp(path + 1)) / h
        return dp(0)

ob = Solution()
print(ob.solve(2, 2, 10))

入力

2, 2, 10

出力

0.11

ロジックのポイント

dp(path) は「現在のポイントが path のときに、最終的なスコアが n 以下でゲームが終わる確率」を表しています。

• path = k − 1 の場合：あと1回の抽選でゲームが終了します。スコアが n を超えないためには、次に引く数が n − (k − 1) = n − k + 1 以下である必要があります。1〜h の中でこれを満たすのは min(n − k + 1, h) 通りなので、確率はそれを h で割った値になります。
• path > n の場合：すでに n を超えているため、確率は 0 です。
• path ≥ k の場合：ゲームは正常に終了しており、確率は 1 です。
• それ以外の場合：以降の状態の確率を組み合わせた漸化式 dp(path + 1) − (dp(path + h + 1) − dp(path + 1)) / h で求めます。

このように再帰的に状態を辿ることで、複雑な確率計算をシンプルなコードで表現できます。ゲーム系の確率問題では頻出するパターンなので、ぜひ覚えておきましょう。