きままにものづくり

日々の気付いたことなんかを書いてます。

SRM642Div1Easy

問題

素数Nのtime、probの2つの数列と整数sが与えられる。バス停を考える。バスiが選択される確率はprob_i / 100であり、戻ってくるのにtime_iの時間がかかる。一つのバスが出発しそのバスが戻ってきたら、バスを選択しまた出発する。バス停を離れているバスは1つだけとする。時間sにバス停に着いた時、次のバスが来るのに待つ時間の期待値を求めよ。

解法

dfsまたはbfsを用いてs以上となる組み合わせを全探索することで、答えが求まる。しかし、この方法だとO(N^M)かかる。Mはバスの最大時間を示す。
動的計画法を用いることで計算時間を削減できる。時刻tにバスが来る確率は、 time_i前にバスが来る確率にprob_i/100を掛けあわせたものの総和になる。これを最大時間まで続けることで、s以上となる確率の分布を求めることができる。あとはこの分布に、待ち時間を掛けあわせることで答えが求まる。

計算量

 O(NM)
N:要素数
M:最大時間

コード

広告を非表示にする