Grenache's blog

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

2015年08月

問題概要

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

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

考察

  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$をかけたものが求める確率です。

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

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

問題概要

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

いわゆる桁ＤＰの問題です。桁ＤＰはなかなか慣れることができません。。。

解法

「$n$以下の正整数で」という条件と$n$が巨大な数という時点で、桁ＤＰを考えるべきなんだと思います。桁ＤＰは、桁数を1つずつ増やしていって、$j$桁目を考える際に、$j-1$桁目までの状態と$j$桁目の数字としてすべての数字(0～9)を変化させた時の状態をまとめていきます。さらに、これとは別に、$n$の$j$桁目の数字まで(0～nのj桁目の数字)を変化させた場合の2つの漸化式を考えることになります。

今回は、各桁で考慮するべき条件が桁の数の和が$D$の倍数であるものということなので、$D$で割った余りの数だけ状態を考える必要があります。つまり、1つ前の桁までの各桁の数の和を$D$で割った余りの数が$i$になる組合せの数がわかれば、それにその桁の数字を足して$D$で割った余りの数になる組合せの数がわかることになります。

漸化式の定義： $$\begin{eqnarray} dp[(i+k)\mod D][j] & += & dp[i][j-1]\\ dp2[(i+k)\mod D][j] & += & \begin{cases}dp2[i][j-1] & (k=num)\\ dp[i][j-1] & (k\lt num)\\ 0 & (k\gt num)\end{cases} \end{eqnarray}$$

$dp[i][j]$：$j$桁目までの数で、各桁の数の和を$D$で割った余りが$i$となる数の個数。「$j$桁目までの数」とは0～999..99と、0から9が$j$個並んだ数までの計$10^j$個の数を意味する

$dp2[i][j]$：$n$の$j$桁目までの数で、各桁の数の和を$D$で割った余りが$i$となる数の個数。「$n$の$j$桁目までの数」とは$n$が123456789と仮定した場合、その数字の下から$j$桁目までの数値、すなわち$j=3$の場合0～789の数を意味する

$k$は0～9とし、$num$は$n$の$j$桁目の数字とする。
$(0\le i \lt D,\ 0\le j \le nの桁数)$

初期値：$dp[0][0]=1,\ dp2[0][0]=1$

求める解：$dp2[0][n]-1$ (0も$D$の倍数とカウントしているのでその分引く)

このように、各桁の数字を0～9で動かしていって、求めるたい条件がどうなるかを計算していきます。その際に上記のように2つの漸化式に分けて考えるのがポイントです。

考察

桁ＤＰを使えばいいというのはわかるのですが、コンテスト本番でコーディングまで落とし込める自信はまだありません。。。

問題概要

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

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

解法

種類が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}]$が出てきているので、その変形が必要となります。これをＤＰとしてまとめると次ようになります。

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

問題概要

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

解法

まずは、1～6の積が$D$の倍数にならないといけないので、$D$を素因数分解したときに、2,3,5以外の要素が含まれていると確率は0になるということがわかります。したがって、$D$の素因数分解が必要になります。素因数分解は単純に2,3,5それぞれで何回割り切れるのかを計算して、$D=2^I\cdot 3^J\cdot 5^K$と表されるとします。

このように考えると、サイコロを$N$回振った時に出た目の積が、それぞれ$2^I\cdot 3^J\cdot 5^K$よりも多い要素でできている確率と考えられます。$n$回目の試行で$2^i\cdot 3^j\cdot 5^k$だった場合、例えば$n+1$回目の試行で2の目が出る$\frac{1}{6}$の確率分、$2^{i+1}\cdot 3^j\cdot 5^k$になる確率が増えます。このようにすべての目が出る確率を計算していきます。

漸化式の定義： \begin{eqnarray} dp[n+1][i][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (1の目が出たとき）\\ dp[n+1][i+1][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (2の目が出たとき）\\ dp[n+1][i][j+1][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (3の目が出たとき）\\ dp[n+1][i+2][j][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (4の目が出たとき）\\ dp[n+1][i][j][k+1] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (5の目が出たとき）\\ dp[n+1][i+1][j+1][k] & += & \frac{1}{6}\cdot dp[n][i][j][k]\ (6の目が出たとき） \end{eqnarray}

$dp[n][i][j][k]$：サイコロを$n$回振った時、出た目の積が$2^i\cdot 3^j\cdot 5^k$と表される確率
$(0\le n \le N,\ 0\le i \le I,\ 0\le j \le J,\ 0\le k \le K)$

初期値：$dp[0][0][0][0]=1$

求める解：$dp[n][I][J][K]$

ただし、上記漸化式左辺の$i,j,k$の部分は、$i+2=\min\{i+2,I\}$などと考え、$2^{I+2}$などになる確率は$dp[n][I][j][k]$に加えるようにして、$i=I$の時は$2^i$ちょうどではなく、$2^I$以上と表される確率とします。

考察

確率の問題は配るＤＰで足していくといいことが多い気がします。特に今回は$2^I$以上のものをまとめたいので、そちらのほうがわかりやすいと思います。

問題概要

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

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

解法

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

漸化式の定義： $$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回のＤＰ問題を解いて、$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$の部分を変数と見たときの漸化式が成り立ちます。つまり、この問題は下記のようなＤＰと考えることができます。

漸化式の定義： $$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つのＤＰに帰着しましたが、よく考えると意味合いも式もちょっと違うんですね。この記事を書いてみて初めて意識することができました。

このページのトップヘ