きままにものづくり

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

ARC016 C問題

問題

arc016.contest.atcoder.jp

解法

N=10と十分小さいのでbitDPをする。
まだ持っていないカードを当てる時のくじを引く回数の期待値は \frac{1}{w}となる。wはカードを当てる確率である。これに、その時のくじ引きのコストをかけることでコストの期待値が求まる。
次に、あるカードを当てた後に全部のカードを揃えるまでのコストを足し合わせることで答えが求まる。

カードが2枚あるとする。
値は、問題の例1の一部を参考とする。
2 1
2 300
1 0.05
2 0.95
はじめに、カードが一枚足りない状況から全部を揃える時の期待値を求める。
1を得るための期待コストc_{01}は
c_{01} = \frac{300}{0.05}
となる。
同様にして2を得るための期待コストを求める。
c_{10} = \frac{300}{0.95}
この２つを用いて、カードを一枚も持ってない状態からの期待コストを求める。
c_{00} = 300 + 0.95c_{01} + 0.05c_{10}
一つ目の項は、 c_{01}またはc_{10}に遷移するのに必要な期待コストを示し、後ろの2項はその状態から全部のカードをそろえるのに必要なコストを示している。wで割ることで、その時の期待コストを求めることができる。

計算量

O(M^22^N)

コード