Grenache's blog

競技プログラミング初心者です。

カテゴリ: 期待値

問題概要

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

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

解法

このブログで何度か書いてきましたが、条件付き期待値の考え方で期待値の漸化式をたてます。(参考: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 家の解説も参考にしてみてください。

問題概要

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

期待値のところで長い間苦労した問題です。

解法

以前、yukicoder No.65で説明した条件付き期待値を使って計算することになります。まずは確率変数を定義します。

$S=\{x_1,x_2,...,x_N\}$(最初に物が置いてある座標の集合)

$S_i\subseteq S$($S$の部分集合)

$X_{S_i}$:集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数

このような確率変数を定義すると求めたいのは確率変数$X_S$の期待値$\mathrm{E}[X_{S}]$です。

ここで、条件付き期待値の考え方で次にボールをどこに投げるのかによって新しい確率変数$\mathrm{E}[X_{S_i}|Y]$を定義して、その確率分布を示します。

$\mathrm{E}[X_{S_i}|Y]$ $1+\mathrm{E}[X_{S_i-\{x-1\}}]$ $1+\mathrm{E}[X_{S_i-\{x\}}]$ $1+\mathrm{E}[X_{S_i-\{x+1\}}]$ 合計
確率 $\frac{1}{3}$ $\frac{1}{3}$ $\frac{1}{3}$ 1

$Y$:次にボールを座標$x$に投げたときに飛んでいく先の座標

結局、yukicoder No.65と同じように求める期待値は以下になります。

$$\begin{eqnarray} \mathrm{E}[X_{S_i}] & = & \mathrm{E}[\mathrm{E}[X_{S_i}|Y]] \\ & = & 1+\mathrm{E}[X_{S_i-\{x-1\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x+1\}}]\cdot \frac{1}{3} \end{eqnarray}$$

ここで、$S_i-\{x\}$は集合$S_i$に$x$という座標が含まれていたらそれを除いた残りの集合という意味ですが、つまりはボールが飛んで行った先の座標にあった物が倒れた後の状態の期待値で表されるということを意味します。しかし、座標$x$にボールを投げたときに、$x-1,x,x+1$それぞれに必ず物があるとは限りません。座標$x$に物がない場合は、$S_i-\{x\}=S_i$となってしまいます。ということは、先ほどの漸化式の右辺にも$\mathrm{E}[X_{S_i}]$が現れるので、式の変形が必要となります。

また、集合$S_i$の要素は0~15の数値で重複はないので、bitDPが使えます。この後は、集合$S_i$を整数$i$にマッピングして表したとします。

漸化式の定義: $$\begin{eqnarray} dp[i] & = & \min\{1+dp[i\ \scriptsize clear\normalsize(x-1)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}\\ & + & dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3}:x=1,2,...,14\} \end{eqnarray}$$

$dp[i]$:集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数の期待値

$i$:集合$S_i$の要素(0~15の値)を$i$のビットの位置とみなして、要素に含まれる座標のビットを1とした場合の整数。ただし、$S_i\subseteq S$なので、$i\ \&\ \tilde{I}=0$が成り立つ$i$のみ。(最初に物がないところのビットが1になっている$i$の時は計算しない)

$i\ \scriptsize clear\normalsize(x)$:整数$i$の$x$番目のビットを0とした場合の整数

$(0\le i \lt I,\ 0\le x \le 15,\ I$:集合$S$の要素(最初に物がある位置の座標)のビットを全て1とした場合の整数)

初期値:$dp[0]=0$、その他は$INF$(適切な大きな値)

求める解:$dp[I]$

$i$のループですが、$S_i\subset S_j$の時には$i\lt j$が成り立つので、小さい値から$i=1~I$のループを回せばよいことになります。

$x$は倒れる確率が3か所とも同じなので、両端の座標0や15に投げる意味がない(倒れる対象が2か所になってしまうので1つ内側の1や14ほうが回数は少なくて済む)のでループに含めません。また、$x-1,x,x+1$全てに物がない場合も投げても意味がない(無駄に回数が増えるだけ)のでその場合は値の更新はありません。もし、$x-1$に物がない場合は$i=i\ \scriptsize clear\normalsize(x-1)$なので、右辺にも$dp[i]$が現れます。したがって、式を変形して$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{2}$となります。$x-1,x$の2か所に物がない場合は、$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{1}$です。このように$x$のループを回しながら、$i$の値によっては式の変形もしつつ最小値を求める必要があります。

考察

$dp[i\ \scriptsize clear\normalsize(x)]$みたいな表現しましたが、ビットの操作を表現するのはどう書くのがいいのでしょうか?$\&$とか$|$とかビット演算で表すと、長くなって表現しにくいなと。($dp[i\ |\ \tilde{}(1 << x)]$とか。)

問題概要

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

詳細な解説を作問者の方が既に書かれているので、気になったところだけ書きます。

考察

  1. インディケータ確率変数

    求めたい期待値の確率変数を、期待値の線形性を使って$X\{2\}$などの和で表しています。この1つの数字について生き残れば1、生き残らなければ0という確率変数を定義することで、結局確率を求めればよいとなっています。このような確率変数はインディケータ確率変数という名前で参考書籍で紹介している「数学ガール 乱択アルゴリズム」の中に出てきます。

  2. 条件付き確率

    「2 によって消されない」かつ「3 によって消されない」かつ「4 によって消されない」確率の説明の部分が直感的にわかりませんでした。

    「2 によって消されない」を事象$A$、「3 によって消されない」を事象$B$、「4 によって消されない」を事象$C$とすると、求める確率は$\Pr\{A\cap B\cap C\}$です。ここで条件付確率の乗法定理によって次のようになります。

    $$\Pr\{A\cap B\cap C\}=\Pr\{A\}\cdot\Pr\{B|A\}\cdot\Pr\{C|A\cap B\}$$

    事象$A$と事象$C$が独立ではないので、ちょっとややこしくなっています。$\Pr\{A\}=1-p$、事象$A$と事象$B$は独立なので$\Pr\{B|A\}=\Pr\{B\}=1-p$となります。$\Pr\{C|A\cap B\}$は、事象$A$、$B$が起こったという条件の下での事象$C$(4によって消されない)の確率なので、これも単純に$1-p$になります(事象$A$の2によって消されていないのは前提なので)。

    ということで、結局1と自分自身を除いた約数の個数分$1-p$をかけたものが求める確率です。

    条件付き確率を持ち出したことで余計わかりにくくなった気もするのですが、なかなか直感的に理解できない部分なので、こういうところまで考えないとなんかもやもやが残ります。

    確率変数についても、これを持ち出すと難しく見えますが、実はとても素晴らしい概念だと思います。高校数学の時には全然理解できていませんでしたが、確率変数の概念はおすすめです。

問題概要

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

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

解法

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

問題概要

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

試行回数の期待値を求める問題で、yukicoder No.65によく似ていますが、複数の$K$(この問題文では$N$となっていますが、No.65の問題に合わせて$K$を使います)に対して期待値を求めなければいけません。

解法

期待値のDPとしての考え方はyukicoder No.65と同じです。各面が出る確率が$\frac{1}{6}$ではなく、それをサンプルから計算しないといけないという点が特殊です。それぞれの$K$について下記のDPで期待値を求めることができます。

漸化式の定義: $$dp[i]=1+dp[i+1]\cdot p_1+dp[i+2]\cdot p_2+...+dp[i+6]\cdot p_6$$

$dp[i]$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数の期待値$(0\le i \le K,\ p_j:jの目が出る確率)$

初期値:$dp[K]=0,\ dp[i]=dp[K](i\gt K)$

求める解:$dp[0]$

$K=1$の時、$dp[0]=1$

$K=2$の時、$dp[0]=1+dp[1]\cdot p_1,\ dp[1]=1$

となり、サンプルで$K=1~6$の期待値があるので、6回のDP問題を解いて、$K=6$までで$p_1~p_5$までの確率がわかります。さらに、$\displaystyle\sum_{i=1}^{6}p_i=1$なので、$p_6$も求めることができます。

しかし、この問題では50個の$K$について期待値を求めなければいけないので、このままではTLEの可能性があります。

ここで確率変数の定義に立ち返って見ます。

$X_{K,i}$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数

この定義から、$K-i$が同じ値の場合は同じ回数と見なすことができて、$X_{K+j,i+j}=X_{K,i}$が成り立ちます。ここで求めなければいけないのは、それぞれの$K$について、$\mathrm{E}[X_{K,0}]$ですが、No.65の問題で考えた漸化式より、

$$\begin{eqnarray} \mathrm{E}[X_{K,0}] & = & 1+\mathrm{E}[X_{K,1}]\cdot p_1+\mathrm{E}[X_{K,2}]\cdot p_2+...+\mathrm{E}[X_{K,6}]\cdot p_6 \\ & = & 1+\mathrm{E}[X_{K-1,0}]\cdot p_1+\mathrm{E}[X_{K-2,0}]\cdot p_2+...+\mathrm{E}[X_{K-6,0}]\cdot p_6 \end{eqnarray}$$

と、$X_{K,i}$の$K$の部分を変数と見たときの漸化式が成り立ちます。つまり、この問題は下記のようなDPと考えることができます。

漸化式の定義: $$dp2[i]=1+dp2[i-1]\cdot p_1+dp2[i-2]\cdot p_2+...+dp2[i-6]\cdot p_6$$

$dp2[i]$:これまでの合計が0の状態から、合計が$i$になるまでに振ることになる回数の期待値$(p_j:jの目が出る確率)$

初期値:$dp2[i]=0(i\le 0)$

求める解:$dp2[i]$

先ほどは$p_i$についてNo.65の方法で求めるやり方を記載しましたが、サンプルからこの漸化式を使って求めることもできます。

考察

よく似た2つのDPに帰着しましたが、よく考えると意味合いも式もちょっと違うんですね。この記事を書いてみて初めて意識することができました。

このページのトップヘ