[Python] DP ABC184D

Let dp (X, Y, Z) be the answer when there are X gold coins, Y silver coins, and Z bronze coins. When any of X, Y, Z is 100, dp (X, Y, Z) = 0. If not, by considering the three cases of which coin was drawn,

dp(X,Y,Z)=\frac{X}{X+Y+Z}(dp(X+1,Y,Z)+1)+\frac{Y}{X+Y+Z}(dp(X,Y+1,Z)+1)+\frac{Z}{X+Y+Z}(dp(X,Y,Z+1)+1)

It will be. (Probability of drawing gold coins x expected value of the number of operations when drawing gold coins + silver coins ...)

You can find the answer by performing DP according to this formula. Implementation is easy if done by memoization recursion.

Sample code


import sys
sys.setrecursionlimit(10 ** 6)  #Raise the upper limit of recursion


def dfs(x, y, z):  #Memoization recursion
    if dp[x][y][z] >= 0: #If the value is already known, return it as it is.
        ret = dp[x][y][z]
    else:  #If the value is not known, find the value by a recurrence formula.
        ret = 0
        S = x + y + z
        ret += x / S * (dfs(x+1, y, z) + 1)
        ret += y / S * (dfs(x, y+1, z) + 1)
        ret += z / S * (dfs(x, y, z+1) + 1)
        dp[x][y][z] = ret  #Note
    return ret


X, Y, Z = map(int, input().split())
M = 100
dp = [[[-1] * (M + 1) for _ in range(M + 1)] for _ in range(M + 1)]
#Termination condition (initialization)
for i in range(A, M + 1):
    for j in range(B, M + 1):
        for k in range(C, M + 1):
            if i == M or j == M or k == M:
                dp[i][j][k] = 0

# dp(X, Y, Z)The answer that
print(dfs(X, Y, Z))

Recommended Posts

[Python] DP ABC184D
[Python] ABC175D
[Python] UnionFind ABC177D
Solve ABC168D in Python
Solve ABC167-D in Python
[Python] Interval scheduling ABC103D
[Python] Cumulative sum ABC186D
[Python] Binary search ABC155D
Solve ABC159-D in Python
[Python] Dynamic programming ABC015D
[Python] Cumulative sum ABC179D
Python
ABC161D Lunlun Number with python3
[Python] DFS (Depth-first Search) ABC157D
ABC154-E (digit DP) in Python
[Python] How to derive nCk (ABC156-D)
(Python) ABC162-D Consideration log and solution
kafka python
Python basics ⑤
python + lottery 6
Built-in python
Python comprehension
Python technique
Studying python
Python 2.7 Countdown
Python memorandum
Python FlowFishMaster
Python service
python function ①
Python basics
Python memo
ufo-> python (3)
Python comprehension
install python
Python Singleton
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
[Python] [Explanation] AtCoder Typical DP Contest: A Contest
Installing Python 3.4.3.
Try python
Python memo
Precautions when solving DP problems with Python
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Python summary
Start python
[Python] Sort