NKODICEのOCHINCHIN確率問題を動的計画法で解く

はじめに

ここ数日NKODICEというダイスゲームが流行っています。

store.steampowered.com

これはチンチロリンのように日本語が書かれた6面体サイコロを振って美しい日本語を作るゲームですが、ダイスを振って出た目で「お」「ち」「ん」「ち」「ん」を作れると役満のような扱いで特別な演出が発生します。

さてこのゲームで使われる $N$ 個のダイスを振ってOCHINCHINを出す確率はどれくらいでしょうか？
Twitterで確率を求めようとしていた先駆者がいたようです。

このTogetterの最後の方でPythonで総当りで見つけようとしているのを見かけましたが、競技プログラミングをしている自分にとってこれは動的計画法で効率的に解けそうだなという勘が働いたので解いてみました。

遷移式を考える

まずdpの遷移式ですが、 $dp["お"が出た回数]["ち"が出た回数]["ん"が出た回数]$ として
$n$ 回目の状態を $dp$ 、 $n + 1$ 回目の状態を $nextdp$ に持たせるとすると
$dp[p][q][r]$ からは"お", "ち", "ん"以外の目が出る3回分が $nextdp[p][q][r]$ にそのまま遷移し、
以下1回分ずつ $nextdp[p + 1][q][r], nextdp[p][q + 1][r], nextdp[p][q][r + 1]$ に遷移します。

しかし"お"は最大1回、"ち"、"ん"は最大2回分しかカウントしなくても良いため、遷移先のdpは
$nextdp[min(p, 1)][min(q, 2)][min(r, 2)]$
のように考えて良いでしょう。

そして完成したコードが以下の通りです。

コード

def main():
    from copy import deepcopy
    n = int(input())
    zeros = [[[0, 0, 0] for _ in range(3)] for __ in range(2)]
    dp = deepcopy(zeros)
    next_dp = deepcopy(zeros)
    dp[0][0][0] = 1
    denominator = 1
    for i in range(1, n + 1):
        for p in range(2):
            for q in range(3):
                for r in range(3):
                    next_dp[p][q][r] += dp[p][q][r] * 3
                    next_dp[min(p + 1, 1)][q][r] += dp[p][q][r]
                    next_dp[p][min(q + 1, 2)][r] += dp[p][q][r]
                    next_dp[p][q][min(r + 1, 2)] += dp[p][q][r]
        denominator *= 6
        dp = deepcopy(next_dp)
        next_dp = deepcopy(zeros)
        if i >= 5:
            print("{}: {}".format(i, dp[1][2][2] * 100 / denominator))


if __name__ == "__main__":
    main()

結果

入力に20を与えて実行した結果が以下の通りです。

5: 0.38580246913580246
6: 1.6075102880658436
7: 3.9509030635573845
8: 7.480043057460753
9: 12.078177392927907
10: 17.51943102867957
11: 23.534830448017747
12: 29.8595907018606
13: 36.26097443365754
14: 42.550877553100875
15: 48.58818495065594
16: 54.27518067599006
17: 59.551102599117804
18: 64.38482936102443
19: 68.7678454049252
20: 72.70805429154048

16個ダイスを投げれば半分以上の確率でボロンできるようです。
実行速度は $O(N)$ であり、確率が表示上100.0%になる229回まで投げても高速に動作することを確認しています。
(分母とか色々オーバーフローしたりするかと思ったけど問題なさそうだったのでPython賢い*1 )