[Python] Dynamic programming TDPC D

TDPC D

Since it is difficult to process 6 = 2 * 3 to solve as a probability problem (number of cases) in high school mathematics, the method of information mathematics is suitable. Since it has partial structure optimality and subproblem duplication, dynamic programming is considered.

It is difficult to implement the data in the problem as it is, so it needs to be simplified.

Since we are thinking about the product, we only need to consider the exponents of the prime factors 2,3,5 that exist in the dice.

Since $ 10 ^ {18} <2 ^ {60} $, each value considered as an exponent can be 60 or less.

The design of dynamic programming is as follows.

Definition of $ dp [n] [c_2] [c_3] [c_5] $: Probability that the number of prime factors 2,3,5 included in the product of the rolled numbers will be $ c_2, c_3, c_5 $, respectively, when shaken $ n $ times.

dp recurrence formula:

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 initial condition: $ dp [0] [0] [0] [0] = 1 $ (When shaken 0 times, the product of the eyes is 1, so the prime factors do not include any prime numbers) dp[0][*][*][]=0

What you want:

When $ 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]

Implementation is done by the DP distributed by the bottom-up method.

Sample code


n, d = map(int, input().split())

#Factoring the dice roll into 2, 3,Only 5 appear
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,No if there is anything other than 5
if d != 1:
    print(0)
    exit()

#dp initialization
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

#Dice roll 1~Prime factorization of 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] :=Roll the dice i times, 2^c2 * 3^c3 * 5^Probability of becoming c5
for i in range(n):
    # c2,c3,c About 5 and 6 eyes i+Update 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])

Recommended Posts

[Python] Dynamic programming TDPC D
[Python] Dynamic programming TDPC A
[Python] Dynamic programming ABC015D
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Python programming note
Python dynamic typing
Programming in python
Studying dynamic programming ①
Learn dynamic programming in Python (A ~ E)
Calculate 2D IDCT ~ Python
3. 3. AI programming with Python
[Python] Binary Acing 2020D
Competitive programming diary python 20201213
Python programming with Atom
Competitive programming diary python 20201220
Competitive programming with python
Python programming in Excel
LEGO Mindstorms 51515 Python Programming
Competitive programming diary python
Programming with Python Flask
Programming with Python and Tkinter
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Python3 programming functions personal summary
Atcoder Acing Programming Contest Python
Create 3d gif with python3
Python: 3D array image (numpy.array)
Python Selenium Dynamic download wait
Python web programming article summary
python> Handling of 2D arrays
Paiza Python Primer 1 Learn Programming
Solve ABC175 D in Python
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Python Competitive Programming Site Summary
Python Machine Learning Programming> Keywords
Python Programming Workshop-Super Introductory Vol.4
[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)
Memoization recursion and dynamic programming known by Python Fibonacci sequence
An introduction to Python Programming
AtCoder ABC 182 Python (A ~ D)
Network programming with Python Scapy
Python 2D array trap [Copy array]
[Swift / Ruby / Python / Java] Object-oriented programming
Python3 standard input for competitive programming
Functional programming in Python Project Euler 1
[Introduction to Python3 Day 1] Programming and Python
3D skeleton structure analysis with Python
[Python] [Table of Contents Links] Python Programming
Dynamic proxy with python, ruby, PHP
Easy Python + OpenCV programming with Canopy
Reinforcement learning 3 Dynamic programming / TD method
Functional programming in Python Project Euler 2
python documentation reading socket programming HOWTO
Python Programming Workshop-Super Introductory Python Execution Environment
I'm addicted to Python 2D lists
[Python scipy] Upscale / downscale 2D data