Hatena::Grouptopcoder

hotpepsiの練習帳

2014-06-30

SRM 626

| 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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140630