[Python] DP ABC184D - Qiita

ABC184D X,Y,Zのいずれかが100のときdp(X,Y,Z)=0 です。そうでないとき、どの硬貨を引いたか3通りの場合を考えることで、 dpの定義： 金貨がX枚、銀貨がY枚、銅貨がZ枚のときの答え dp漸化式の定義： $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)$ dp終端条件： $dp(M,M,M)=0$ となります。（金貨を引く確率×金貨を引いた時の操作回数の期待値＋銀貨を……） この式に従ってDPを行うと答えを求めることができます。実装はメモ化再帰により行うと容易です。 import sys sys.setrecursionlimit(10 ** 6) # 再帰数上限の引き上げ def dfs(x, y, z)