hotpepsiの練習帳

SRM 626

DP | 01:29

Div1 Easy (250) FixedDiceGameDiv1

問題

• Aliceはa個のb面ダイスを振る
• Bobはc個のd面ダイスを振る
• n面ダイスは1からnの値を持つ
• 出目の合計の多いほうが勝ち
• Aliceが勝つときの期待値を求める

方針

• nCkでやるとたぶん死ぬ
• dp[N回振った][合計値]で確率のテーブルは作れそう
• AliceとBobのテーブルを作っておく
• Aliceの合計値がN回のときの確率をPa、Bobの合計値が1からN-1までの確率をPbとする
• 全事象に対する生起確率Pn＝Pa×Pb
• PnにNを重み付けして、Pnの和で割れば期待値になりそう
• (N×Pnの和)÷(Pnの和)が答え
• Passed System Test

https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_626/FixedDiceGameDiv1.cpp

結果

o-- 107.91pts 359th/739 rating 1522 -> 1539 (+17)

外は寒かった。家でやるべき。

http://togetter.com/li/686090