解法
N=10と十分小さいのでbitDPをする。
まだ持っていないカードを当てる時のくじを引く回数の期待値はとなる。wはカードを当てる確率である。これに、その時のくじ引きのコストをかけることでコストの期待値が求まる。
次に、あるカードを当てた後に全部のカードを揃えるまでのコストを足し合わせることで答えが求まる。
カードが2枚あるとする。
値は、問題の例1の一部を参考とする。
2 1
2 300
1 0.05
2 0.95
はじめに、カードが一枚足りない状況から全部を揃える時の期待値を求める。
1を得るための期待コストは
となる。
同様にして2を得るための期待コストを求める。
この２つを用いて、カードを一枚も持ってない状態からの期待コストを求める。
一つ目の項は、または
に遷移するのに必要な期待コストを示し、後ろの2項はその状態から全部のカードをそろえるのに必要なコストを示している。wで割ることで、その時の期待コストを求めることができる。
計算量