Pythonでn個のサイコロの出目の合計がtotalになる組み合わせの数を求めるプログラム

本記事では、サイコロの個数 n、各サイコロの面の数 faces、そして目標となる合計値 total が与えられたとき、n 個のサイコロを振った結果の合計が total と一致する組み合わせが何通りあるかを求める問題を解説します。答えが非常に大きな数になる可能性があるため、結果は 10⁹ + 7 で割った余りとして返します。

例えば、入力が n = 2、faces = 6、total = 8 の場合、出力は 5 になります。これは、2つの6面ダイスで合計8を作る方法が次の5通り存在するためです。

• (2 と 6)
• (6 と 2)
• (3 と 5)
• (5 と 3)
• (4 と 4)

解法のアプローチ:動的計画法(DP)

この問題は動的計画法を用いることで効率的に解けます。dp[j] を「これまでに振ったサイコロで合計 j を作る組み合わせの数」と定義し、サイコロを1個ずつ追加しながら表を更新していきます。具体的な手順は以下の通りです。

• m := 10⁹ + 7(剰余演算用の定数)を設定する
• サイズ (total + 1) のリスト dp を作成し、すべて 0 で初期化する
• face を 1 から min(faces, total) まで順に処理し、dp[face] := 1 とする(1個目のサイコロでその出目を出す方法は1通りだけ)
• i が 0 から n - 2 までの範囲で、以下を繰り返す:
• • j を total から 1 まで逆順に走査する
  • dp[j] を「f が 1 以上 faces 以下で、j - f ≥ 1 を満たすすべての dp[j - f] の総和」で更新する
• 最後に dp の末尾の要素を m で割った余りを返す

j を逆順に更新することで、同じサイコロを複数回使ってしまうことを防ぎ、1次元配列だけで状態を管理できる点がポイントです。

実装例

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

class Solution:
   def solve(self, n, faces, total):
      m = 10 ** 9 + 7
      dp = [0] * (total + 1)

      for face in range(1, min(faces, total) + 1):
         dp[face] = 1
      for i in range(n - 1):
         for j in range(total, 0, -1):
            dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1)
      return dp[-1] % m
ob = Solution()
n = 2
faces = 6
total = 8
print(ob.solve(n, faces, total))

入力

2,6,8

出力

5

計算量の評価

このアルゴリズムの時間計算量は O(n × total × faces)、空間計算量は O(total) です。サイコロの個数や合計値が大きくなっても、全通りを列挙する指数的な探索に比べれば大幅に効率的であり、競技プログラミングなどでも広く使われる定番のテクニックです。