C++で解くダイスロールシミュレーション ― 連続出現制約付きサイコロ問題をDFSとDPで効率的に解く方法

問題の概要

サイコロシミュレーターは、1回のロールごとに1から6までのランダムな数値を生成します。ここで、「同じ数字 i を rollMax[i] 回(1-indexed)より多く連続して出してはならない」という制約をジェネレーターに導入することを考えます。整数型の配列 rollMax と整数 n が与えられたとき、ちょうど n 回のロールで得られる異なる出目列(シーケンス)の総数を返してください。2つのシーケンスは、少なくとも1つの要素が異なっていれば別のものとみなされます。

例えば、n = 2、rollMax = [1,1,2,2,2,3] の場合、答えは 34 になります。サイコロを2回振るとき、制約がなければ 6 × 6 = 36 通りの組み合わせが存在します。しかし、このケースでは数字 1 と 2 は連続して最大1回しか出現できないため、(1,1) と (2,2) というシーケンスは発生しません。したがって、最終的な答えは 36 − 2 = 34 となります。

解法のアプローチ

この問題は、メモ化再帰(DFS + 動的計画法)を使うことで効率的に解けます。手順は以下の通りです。

• dfs() メソッドを作成します。引数は dieLeft(残りのロール回数)、last(直前の出目)、currLen(直前の出目の連続回数)、配列 r、3次元行列 dp です。
• dieLeft = 0 の場合は 1 を返します(有効なシーケンスが1つ完成したことを意味します)。
• dp[dieLeft][last][currLen] が -1 でない場合は、その値をそのまま返します(メモ化による高速化)。
• counter を 0 で初期化します。
• i を 0 から 5 までループします。
  • i == last かつ r[i] == currLen の場合は、その反復をスキップします(連続出現の上限に達しているため)。
  • counter := dfs(dieLeft − 1, i, i == last ? currLen + 1 : 1, r, dp)
• dp[dieLeft][last][currLen] := counter
• dp[dieLeft][last][currLen] を返します。

メインメソッドは次のように実装します。

• (n + 1) × 6 × 16 のサイズを持つ3次元配列 dp を作成し、すべての要素を -1 で初期化します。
• dfs(n, 0, 0, rollMax, dp) の結果を返します。

それでは、実際の実装例を見ながら理解を深めましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
class Solution {
public:
    int dfs(int dieLeft, int last, int currLen, vector<int> &r, vector<vector<vector<int>>> &dp){
        if(dieLeft == 0){
            return 1;
        }
        if(dp[dieLeft][last][currLen] != -1) return dp[dieLeft][last][currLen];
        int counter = 0;
        for(int i = 0; i < 6; i++){
            if(i == last && r[i] == currLen) continue;
            counter = (counter % mod + (dfs(dieLeft - 1, i, i == last ? currLen + 1 : 1, r, dp)) % mod) % mod;
        }
        dp[dieLeft][last][currLen] = counter % mod;
        return dp[dieLeft][last][currLen] % mod;
    }
    int dieSimulator(int n, vector<int>& rollMax) {
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(16, -1)));
        return dfs(n, 0, 0, rollMax, dp) % mod;
    }
};
main(){
    vector<int> v = {1,1,2,2,2,3};
    Solution ob;
    cout << (ob.dieSimulator(2, v));
}

入力

2
[1,1,2,2,2,3]

出力

34

計算量の目安

状態の総数は O(n × 6 × 16)、各状態から最大6通りの遷移が発生するため、時間計算量は O(n × 6 × 16 × 6)、空間計算量は O(n × 6 × 16) となります。メモ化によって同じ状態の再計算を避けられるため、n が大きくなっても高速に動作するのが特徴です。