hotpepsiの練習帳

SRM 642

02:25

Div1 Easy (250) WaitingForBus

問題

• N台のバスがある
• ランダムでどれかのバスが出発する
• 戻ってきたら次のバスがランダムで選ばれる
• バスが選ばれる確率と、戻ってくるまでの時間の配列が与えられる
• 時刻sでの平均待ち時間を求める

方針

• 時刻ゼロの時は待ち時間なし
• 確率で重みづけして到着時刻の位置に加算していく
• 時刻sまで計算する
• 時刻sより先のtに確率pでバスが存在するなら期待値は(t-s)*p
• 期待値の和が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_642/WaitingForBus.cpp

結果

o-- 192.21pts 133rd/367 rating 1298 -> 1382 (+84)

誤差恐怖症なのでlong doubleにした。

もしバスのスケジュールがこんなだったらタクシーに乗る。

http://togetter.com/li/758671