SRM462 div1 250

問題

バス停からn台のバスが確率的に選ばれて1台だけ出発し、そのバスが戻ってくるまで他のバスは出発できない。
バスiは、戻ってくるまでtime[i]時間だけかかる。また、バスiはprob[i]/100の確率で選ばれる。
バス停に時刻sで訪れた時にバスの出発までに待たなければならない時間の期待値を求めよ。

n<=100
time[i] <= 10^5
prob[i] <= 100
s <= 10^5

考え方

愚直に全パターンを求めるとO(N^N)程度確認する必要があるので、TLE。

dp[i]:=時刻iにバスがちょうど戻ってくる確率
がわかると、(i-s)時刻だけ待つ確率がdp[i]で求まるので、s以上のiについて、dp[i] * (i-s)を足し合わせればよい。
dp[i]は時刻sを超えたiから出発する分については考える必要がないので、0〜sから出発する場合のみ考えればよく、時刻iでバスjを使う場合、dp[i+time[j]] += dp[i] * prob[j]で求めていける。