問題概要

問題文はこちらを参照してください。

いわゆるコンプガチャ問題の変形だと思います。。

解法

種類が100種類ということなので、どの種類を持っているのかという状態の区別をすると無理というのがわかります(20個程度だとbitDPの可能性)。なので、状態として1枚以上持っている種類数、2枚以上持っている種類数などを考えて、1回の試行によって1枚以上持っている種類数が1増えるか2枚以上持っている種類数が1増えるという状態の変化を考えてみます。

ここで、求めたい期待値の確率変数を次のように定義します。

$X_{ijk}$:1枚以上持っている種類数が$i$、2枚以上持っている種類数が$j$、3枚以上持っている種類数が$k$としたときに、3枚以上持っている種類数が$n$になるまでにカードを買う回数。ただし、$i\ge j\ge k$が成り立つ

このように考えると、1回の試行によって0枚持っている種類を引く、1枚持っている種類を引く、2枚持っている種類を引く、3枚以上持っている種類を引くの4通りのケースが考えられるので、$X_{ijk}$の条件付き期待値をもとに、確率変数$\mathrm{E}[X_{ijk}|Y]$の確率分布を表で表します。

$\mathrm{E}[X_{ijk}|Y]$ $1+\mathrm{E}[X_{i+1jk}]$ $1+\mathrm{E}[X_{ij+1k}]$ $1+\mathrm{E}[X_{ijk+1}]$ $1+\mathrm{E}[X_{ijk}]$ 合計
確率 $\frac{n-i}{n}$ $\frac{i-j}{n}$ $\frac{j-k}{n}$ $\frac{k}{n}$ 1

結局、No.65の解説にあったように、条件付き期待値の公式から、求める期待値は次のようになります。

$$\begin{eqnarray} \mathrm{E}[X_{ijk}] & = & \mathrm{E}[\mathrm{E}[X_{ijk}|Y]]\\ & = & 1+\mathrm{E}[X_{i+1jk}])\frac{n-i}{n}+\mathrm{E}[X_{ij+1k}])\frac{i-j}{n}+\mathrm{E}[X_{ijk+1}])\frac{j-k}{n}+\mathrm{E}[X_{ijk}])\frac{k}{n} \end{eqnarray}$$

ただし、右辺にも$\mathrm{E}[X_{ijk}]$が出てきているので、その変形が必要となります。これをDPとしてまとめると次ようになります。

漸化式の定義: $$ \begin{eqnarray} dp[i][j][k] & = & \{1+dp[i+1][j][k]\cdot \frac{n-i}{n}+dp[i][j+1][k]\cdot \frac{i-j}{n}\\ & + & dp[i][j][k+1]\cdot \frac{j-k}{n}\}/\frac{n-k}{n}\ (i\lt n)\\ dp[i][j][k] & = & \{1+dp[i][j+1][k]\cdot \frac{i-j}{n}\\ & + & dp[i][j][k+1]\cdot \frac{j-k}{n}\}/\frac{n-k}{n}\ (i=n,\ j\lt n)\\ dp[i][j][k] & = & \{1+dp[i][j][k+1]\cdot \frac{j-k}{n}\}/\frac{n-k}{n}\ (i=n,\ j=n,\ k\lt n) \end{eqnarray}$$

$dp[i][j][k]$:1枚以上持っている種類数が$i$、2枚以上持っている種類数が$j$、3枚以上持っている種類数が$k$としたときに、3枚以上持っている種類数が$n$になるまでにカードを買う回数の期待値$(0\le k \le n,\ k\le j \le n,\ j\le i \le n)$

初期値:$dp[n][n][n]=0$

求める解:$dp[$最初の状態で1枚以上持っている種類数$][$最初の状態で2枚以上持っている種類数$][$最初の状態で3枚以上持っている種類数$]$

考察

x枚以上持っている種類数でまとめるのがすぐ思いつけるようになるのでしょうか。。。場数をどんだけこなすかなんですかね。