srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

モンテカルロ法

yukicoder No.58 イカサマなサイコロ

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

yukicoder No.173 カードゲーム(Medium)

問題 問題概要 省略 解法 誤差の許容が大きいため、モンテカルロ法を使えばいいらしい。やっていることは、確率pで1枚目を選ぶとあるので、乱数で0~1までだし、pより小さければ1枚目を選び、そうでなければ、その他のものを等しい確率で選ぶというシミュレー…