SRM642Div1Easy
問題
要素数Nのtime、probの2つの数列と整数sが与えられる。バス停を考える。バスiが選択される確率はであり、戻ってくるのに
の時間がかかる。一つのバスが出発しそのバスが戻ってきたら、バスを選択しまた出発する。バス停を離れているバスは1つだけとする。時間sにバス停に着いた時、次のバスが来るのに待つ時間の期待値を求めよ。
解法
dfsまたはbfsを用いてs以上となる組み合わせを全探索することで、答えが求まる。しかし、この方法だとかかる。Mはバスの最大時間を示す。
動的計画法を用いることで計算時間を削減できる。時刻tにバスが来る確率は、前にバスが来る確率に
を掛けあわせたものの総和になる。これを最大時間まで続けることで、s以上となる確率の分布を求めることができる。あとはこの分布に、待ち時間を掛けあわせることで答えが求まる。
計算量
N:要素数
M:最大時間
