Official
D - increment of coins Editorial by kyopro_friends
この問題は確率DPと呼ばれるジャンルの問題です。
金貨が \(X\) 枚、銀貨が \(Y\) 枚、銅貨が \(Z\) 枚のときの答えを \(f(X,Y,Z)\) とします。\(X,Y,Z\)のいずれかが100のとき \(f(X,Y,Z)=0\) です。そうでないとき、どの硬貨を引いたか3通りの場合を考えることで、
\[ f(X,Y,Z)= \frac{X}{X+Y+Z}(f(X+1,Y,Z)+1) +\frac{Y}{X+Y+Z}(f(X,Y+1,Z)+1) +\frac{Z}{X+Y+Z}(f(X,Y,Z+1)+1) \]
となります。(金貨を引く確率×金貨を引いた時の操作回数の期待値+銀貨を……)
この式に従ってDPを行うと答えを求めることができます。実装はメモ化再帰により行うと容易です。
posted:
last update: