SRM642 Div1 Easy WaitingForBus

競技プログラミング C++ TopCoder

TopCoder Statistics - Problem Statement

[問題]

バス発着所にN台のバスがある。それぞれのバスは出発するとtime[i]後にバス発着所に帰ってくる。時刻0にいずれかのバスが確率prob[i]で出発し、戻ってくるといずれかの次のバスが同じく確率prob[i]で出発し、、、を繰り返す。

時刻sにバス発着所に着いた時、待ち時間の期待値はどれぐらいか？

1≤N≤100

1≤time[i]≤10^5

1≤prob[i]≤100

0≤s≤10^5

 

[解答]

dp[時刻]である時点でバスの出発時刻である確率を保持して時刻s以上の最初の時点(最大s+10^5)までDPで更新していく。sからs+10^5の間の Σ DP[i]x(i-s) で期待値を求める。計算量はO(s * N)

[コード](C++)