1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] 動的計画法 TDPC D

Last updated at Posted at 2021-01-01

#TDPC D

高校数学の確率問題(場合の数)として解くのは、6=2*3の処理が難しいので、情報数学の手法が適している。
部分構造最適性と部分問題重複性を有するので、動的計画法を検討する。

問題内のデータをそのまま実装するのは難しいので、単純化する必要がある。

積について考えるので、サイコロの目に存在する素因数 2,3,5 の指数のみを考えれば良い。

$10^{18}<2^{60}$ なので、指数として考える値はそれぞれ 60 以下でよいです。

動的計画法の設計は次の通り。

$dp[n][c_2][c_3][c_5]$の定義:
$n$ 回振ったときに、出た目の積に含まれる素因数 2,3,5 の個数がそれぞれ$c_2,c_3,c_5$となる確率

dpの漸化式:

dp[n][nc_2][nc_3][nc_5]=\sum_{i=0}^{n-1}\sum_{c_2\ge nc_2, c_3 \ge nc_3, c_5 \ge nc_5}dp[i][c_2][c_3][c_5]

dp初期条件:
$dp[0][0][0][0]=1$(0 回振ったとき、目の積を 1 とするので、素因数にいかなる素数も含まれない)
$dp[0][][][]=0$

求めるもの:

$D=2^a 3^b 5^c$のとき

\sum_{p_2\ge a, p_3 \ge b, p_5 \ge c}dp[N][p_2][p_3][p_5]

実装は、ボトムアップ方式の配るDPで行う。

サンプルコード
n, d = map(int, input().split())

# サイコロの目を素因数分解すると、2, 3, 5しか現れない
count2 = 0
count3 = 0
count5 = 0
while d % 2 == 0:
    d //= 2
    count2 += 1
while d % 3 == 0:
    d //= 3
    count3 += 1
while d % 5 == 0:
    d //= 5
    count5 += 1

# 2, 3, 5以外があったらだめ
if d != 1:
    print(0)
    exit()

# dp初期化
dp = [[[[0] * (count5 + 1) for i in range(count3 + 1)] for j in range(count2 + 1)] for k in range(n + 1)]
dp[0][0][0][0] = 1

# サイコロの目1~6を素因数分解
d2 = [0, 1, 0, 2, 0, 1]
d3 = [0, 0, 1, 0, 0, 1]
d5 = [0, 0, 0, 0, 1, 0]

# dp[i][c2][c3][c5] := サイコロを i 回振って、2^c2 * 3^c3 * 5^c5 になる確率
for i in range(n):
    # c2,c3,c5および6つの目についてi+1のdpを更新
    for c2 in range(count2 + 1):
        for c3 in range(count3 + 1):
            for c5 in range(count5 + 1):
                for j in range(6):
                    nc2 = min(count2, c2 + d2[j])
                    nc3 = min(count3, c3 + d3[j])
                    nc5 = min(count5, c5 + d5[j])
                    dp[i + 1][nc2][nc3][nc5] += dp[i][c2][c3][c5] / 6

print(dp[n][count2][count3][count5])
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?