No.108

$i$ 枚 ($0 \leq i \leq 2$) 持っているカードの種類数を $x_i$ として, このときのコンプリートまで購入するカード枚数の期待値を $E(x_0, x_1, x_2)$ とすると,

$$E(x_0, x_1, x_2) = E(x_0 - 1, x_1 + 1, x_2) \frac{x_0}{N} + E(x_0, x_1 - 1, x_2 + 1) \frac{x_1}{N} + E(x_0, x_1, x_2 - 1) \frac{x_2}{N} + E(x_0, x_1, x_2) \frac{N - x_s}{N} + 1$$

s.t.

$$x_s = x_0 + x_1 + x_2$$

となる. これを変形して,

$$E(x_0, x_1, x_2) = (E(x_0 - 1, x_1 + 1, x_2) x_0 + E(x_0, x_1 - 1, x_2 + 1) x_1 + E(x_0, x_1, x_2 - 1) x_2 + N) \frac{1}{x_s}$$

s.t.

$$E(0, 0, 0) = 0$$

となる.

これをメモ化再帰で計算する.