Grenache's blog

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

問題概要

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

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

解法

「$n$以下の正整数で」という条件と$n$が巨大な数という時点で、桁DPを考えるべきなんだと思います。桁DPは、桁数を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つの漸化式に分けて考えるのがポイントです。

考察

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

問題概要

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

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

解法

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

問題概要

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

解法

まずは、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$以上と表される確率とします。

考察

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

このページのトップヘ