問題概要

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

最初、解説を見ても全然わかりませんでした。期待値をちゃんと勉強しなければいけないと思わせてくれた、きっかけの問題です。

解法

このブログで何度か書いてきましたが、条件付き期待値の考え方で期待値の漸化式をたてます。(参考:yukicoder No.65の解説TDPC J ボールの解説)

集合$S_i$で表されるアイドルが集まっている状態から、$j$番目のくじを引くとします。確率変数$X_{S_i}$を集合$S_i$のアイドルが集まっている状態からすべてのアイドルを集めるために必要な金額とすると、条件付き期待値の考え方で新たな確率変数$\mathrm{E}[X_{S_i}|Y]$が定義できて、その確率分布は次のようになります。

$\mathrm{E}[X_{S_i}|Y]$ $\begin{eqnarray}&&cost_j\\&&+\mathrm{E}[X_{S_i\cup \{idol_{j,1}\}}]\end{eqnarray}$ $\begin{eqnarray}&&cost_j\\&&+\mathrm{E}[X_{S_i\cup \{idol_{j,2}\}}]\end{eqnarray}$ ... $\begin{eqnarray}&&cost_j\\&&+\mathrm{E}[X_{S_i\cup \{idol_{j,C_j}\}}]\end{eqnarray}$ 合計
確率 $\frac{p_{j,1}}{100}$ $\frac{p_{j,2}}{100}$ ... $\frac{p_{j,C_j}}{100}$ 1

$S_i$:$S_i\subseteq S$、$S=\{idol_1,idol_2,...,idol_N\}$(全アイドルの集合)

$Y$:$j$番目のくじを引いたときに得られるアイドルの番号$idol_{j,y}$

従って、求めたい$X_{S_i}$の期待値は次のようになります。 $$\begin{eqnarray} \mathrm{E}[X_{S_i}] & = & \mathrm{E}[\mathrm{E}[X_{S_i}|Y]]\\ & = & cost_j+\mathrm{E}[X_{S_i\cup \{idol_{j,1}\}}]\cdot \frac{p_{j,1}}{100}+\mathrm{E}[X_{S_i\cup \{idol_{j,2}\}}]\cdot \frac{p_{j,2}}{100}+...\\ & + & \mathrm{E}[X_{S_i\cup \{idol_{j,C_j}\}}]\cdot \frac{p_{j,C_j}}{100} \end{eqnarray}$$

これをすべての種類のくじについて行ってみて、期待値が一番小さくなるくじを選ぶのが最適な戦略となります。また、この漸化式では例えば$idol_{j,1}$が既に集合$S_i$に含まれている場合は、$\mathrm{E}[X_{S_i}]=\mathrm{E}[X_{S_i\cup \{idol_{j,1}\}}]$となるので、漸化式を次のように変形して$\mathrm{E}[X_{S_i}]$を計算する必要があります。

$$\frac{100-p_{j,1}}{100}\cdot\mathrm{E}[X_{S_i}]=cost_j+\mathrm{E}[X_{S_i\cup \{idol_{j,2}\}}]\cdot \frac{p_{j,2}}{100}+...+\mathrm{E}[X_{S_i\cup \{idol_{j,C_j}\}}]\cdot \frac{p_{j,C_j}}{100}$$

さらに、あるくじで得られるすべてのアイドルが集合$S_i$に含まれている場合は、そのくじを引いてもアイドルが増えることがないので引く必要はありません。(計算しない)

漸化式の定義: $$\begin{eqnarray} dp[S_i] & = & \min\{cost_j+dp[S_i\cup\{idol_{j,1}\}]+dp[S_i\cup\{idol_{j,2}\}]+...\\ & + & dp[S_i\cup\{idol_{j,C_j}\}]:j=1,2,...,M\} \end{eqnarray}$$

$dp[i]$:集合$S_i$で表されるアイドルが集まっている状態から、全てのアイドルを集めるために必要な金額の期待値

$S_i$:集まっているアイドルの番号(0-indexedに変更)の集合。($\{0,2,5\}$など)

$i$:集合$S_i$の要素(0~N-1の値)を$i$のビットの位置とみなして、要素に含まれるアイドルの番号のビットを1とした場合の整数。

$j$:$j$番目のくじを引く場合。

$(0\le i \lt 2^N,\ 0\le j\lt M)$

初期値:$dp[S(全アイドル)]=0$、その他は$INF$(適切に大きな値)

求める解:$dp[0]$

集合については例によってbitDPで計算します。$i$のループは貰うDPで、$2^N-1$から$0$に回して計算していけばよいです。$j$番目のくじに含まれるアイドルが$S_i$にすでに入っているかどうかをチェックしながら、式の変形もしつつ計算をしていきます。

考察

期待値の漸化式が理解できると何とかなる問題ですが、本当に最初は全く分かりませんでした。

bitDPの部分はTDPC M 家の解説も参考にしてみてください。