1056 Ben Toh

あいづおんらいんじゃっぢ

UAPC2010の復習。

1056

1日ぐらい考えてたけど全然わからなかったので、解答(http://d.hatena.ne.jp/Tayama/20100602/1275487902)見てしまった。が、それでも微妙なところ。難しい。


とりあえず数日分書きだす。DPっぽい。
DP[日][獲得してる弁当数]でいいかな？→参照するところ多すぎだし、よくわからない。
解答見る。DP[日][その日まで連続getした弁当数]？

E(n日間で弁当を得られる個数)
=E( (1日目に得られる個数)+...+(n日目に得られる個数) )
=E(1日目に得られる個数)+...+E(n日目に得られる個数)
ってことでいいのかな。。。

DPは、i日目にj個連続getしている確率DP[i][j]から(i+1)日目を考えると、(i+1)日目にgetできる場合、j個連続ゲットできる確率pから(p/2)*DP[i][j]がDP[i+1][j+1]に加算して、getできない場合は(1-p/2)*DP[i][j]がDP[i+1][0]に加算する。

i日目で弁当が得られる期待値は、DP[i][0]がその日得られない確率なので、弁当1個*(1-DP[i][0])。それをn日まで繰り返す。
さらに、nが大きい時メモリも時間も足りないので、連続get数が大きい時の確率が小さくなることを利用して、DP[i][100]程度にする。みたい。

って感じでいいのかどうか。。。
とりあえず、まだ今の自分にはとても難しい。問題解いて慣れるしかないのかな。