Grenache's blog

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

問題概要

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

ＤＰの問題というよりも、組み合わせの数を数える部分の理解に苦労しました。期待値の時もそうなんですが、確率の勉強大事。

解法

まずは下記のような具体的な例を考えます。頂点$i,j$の辺があるとして、頂点$j$の右側に連結を保ちながら辺を描く順番を考えます。

typicalDPN

実際には、辺を描く順番としてACDEB, ACDBE, ACBDE, ABCDE, BACDE, ADCEB, ADCBE, ADBCE, ABDCE, BADCE, ACEDB, ACEBD, ACBED, ABCED, BACEDの15通りになります。連結を保つという制限がなければ、辺を描く順番の組み合わせの数は辺の数分の並べ替えで$5!$通りですが、Aよりも先にその右側にある辺(C,D,E)を描けない、Cよりも先にその右側にあるEを描けないという組み合わせ分を除かなければいけません。

ここで、辺Aが既にあるとして、頂点$1$の右側に連結を保ちながら辺を描く順番の組み合わせがわかっている(実際は3通り)とします。すると先ほど考えた5つの辺の並べ替えのうち、ACDEの部分は先頭がAで、残りは3通りしか許されないということになります。つまり、$5!$をACDEの並べ替えの数$4!$で割って、実際に許される組合せの数$3$をかけることで求められます。

$dp[i][j]$を辺$i,j$があるとして、頂点$j$の右側に連結を保ちながら辺を描く組合せの数とし、$vn[i][j]$を頂点$i$を親側と見て、頂点$j$の配下にある辺の数とします。すると次の式が成り立ちます。

$$dp[i][j]=vn[j][j]!\cdot\frac{dp[j][1]}{(vn[j][1]+1)!}\cdot\frac{dp[j][2]}{(vn[j][2]+1)!}$$

(頂点1側の辺を描く組み合わせは$(vn[j][1]+1)!$通りあるが、条件を満たすのはそのうち$dp[j][1]$通りだけ。頂点2側も同様)

このように、$dp[i][j]$は頂点$j$の配下の辺に関する部分問題$dp[j][1],dp[j][2]$を使って解くことができます。

漸化式の定義： $$dp[i][j]=vn[i][j]!\cdot\prod_{k}\frac{dp[j][k]}{(vn[j][k]+1)!}$$ $$vn[i][j]=\sum_{k}vn[j][k]+1$$

$dp[i][j]$：辺$i,j$があるとして、頂点$j$の右側に連結を保ちながら辺を描く組合せの数。

$vn[i][j]$：頂点$i$を親側と見たとして頂点$j$の配下にある辺の数。

$k$：頂点$j$からつながる頂点のうち、頂点$i$ではないもの(頂点$i$を親側と見たとして、頂点$j$の子となる頂点)。$E$を木の辺の集合としたとき、辺$(j,k)\in E$かつ$k\ne i$を満たす。

$i,j$：辺$(i,j)\in E\ $($i$と$j$を入れ替えたものも含めて$2(n-1$個)

初期値：条件を満たす$k$が存在しないとき(頂点$j$が葉であるとき)、$dp[i][j]=1$,$vn[i][j]=0$

この漸化式からボトムアップのループを決めるのは自分には無理なので、実装はメモ化再帰を用いました。

また、階乗の計算が出てきますが、それはすべて辺の数になっているので$n-1$を超えることがありません。これについては事前に$fact[n]$などとして、$n!$を$MOD$で割った余りを$O(n)$で計算することができます。また、階乗の割り算も出てきますが、こちらについては素数での剰余なので、$ifact[n]$などとして、$n!$の逆元を同様に求めておきます。

これで定義した$dp[i][j]$については求まりますが、最終的な解は次のようになります。先ほどと同じように辺$i,j$の右に$vn[i][j]$個の辺があって、条件を満たす組合せは$dp[i][j]$個、また、左には$vn[j][i]$個の辺があって、条件を満たす組合せは$dp[j][i]$個。したがって、辺$i,j$を最初に描いた時の組み合わせの数は$(vn[i][j]+vn[j][i])!\cdot\frac{dp[i][j]}{vn[i][j]!}\cdot\frac{dp[j][i]}{vn[j][i]!}$となります。これをすべての辺について足したものが解になります。

$\displaystyle\sum_{辺(i,j)\in E}(vn[i][j]+vn[j][i])!\cdot\frac{dp[i][j]}{vn[i][j]!}\cdot\frac{dp[j][i]}{vn[j][i]!}$($n-1$個の辺についての和)

考察

$dp[i][j]$は辺の数の2倍分の組み合わせしか有効ではないですし、$k$のループも全体で辺の数の2倍しかないので、$O(n^2)$にもならないのではないかと思うのですが、ちゃんと計算できないのでわかったら追記しようと思います。

逆元についての詳細は省きますが、組み合わせの数の問題ではぜひ知っておきたい知識だと思います。逆元使わないとこの問題も解けないのではないでしょうか。(Combinationで表してパスカルの三角形でも解けるようです)

問題概要

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

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

解法

このブログで何度か書いてきましたが、条件付き期待値の考え方で期待値の漸化式をたてます。(参考：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$のループは貰うＤＰで、$2^N-1$から$0$に回して計算していけばよいです。$j$番目のくじに含まれるアイドルが$S_i$にすでに入っているかどうかをチェックしながら、式の変形もしつつ計算をしていきます。

考察

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

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

問題概要

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

巡回セールスマン問題(TSP)のようにbitDPで解く必要があります。

解法

同じ構造の階がたくさんあって、降りる方向にしか進めないということなので、ある階において部屋$j$に上から降りてきて、部屋$i$で次の階に降りるまでの経路の数がわかっていて$a_{ij}$とします。また、その階に降りてくる時までの経路の数はわかっていて、それぞれの部屋$j$に降りてきた時の経路の数を$x_j$とします。すると、その階の部屋$i$で次に降りる経路の数は、$\displaystyle\sum_{j=0}^{R-1}a_{ij}\cdot x_j$となります。部屋$i$で次に降りる経路の数を$y_i$とすると、これは行列の積で表すことができます。(部屋番号は0-indexedに変更)

$$\left(\begin{array}{c}y_0 \\ y_1 \\ \vdots \\ y_{R-1}\end{array}\right) = \left( \begin{array}{cccc} a_{00} & a_{01} & \ldots & a_{0R-1} \\ a_{10} & a_{11} & \ldots & a_{1R-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{R-1\ 0} & a_{R-1\ 1} & \ldots & a_{R-1\ R-1} \end{array} \right) \left(\begin{array}{c}x_0\\x_1\\\vdots\\x_{R-1}\end{array}\right)$$

1階分の計算はこのようになるので、この演算を繰り返し行うことで、$H$階分降りたときの経路の数を求めることができます。

$$\left(\begin{array}{c}y_{H0} \\ y_{H1} \\ \vdots \\ y_{H\ R-1}\end{array}\right) = \left( \begin{array}{cccc} a_{00} & a_{01} & \ldots & a_{0R-1} \\ a_{10} & a_{11} & \ldots & a_{1R-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{R-1\ 0} & a_{R-1\ 1} & \ldots & a_{R-1\ R-1} \end{array} \right)^H \left(\begin{array}{c}1\\0\\\vdots\\0\end{array}\right)$$

最初は部屋$0$からスタートするので、$x_0$のみ$1$でそれ以外は$0$、$H$階の部屋$0$まで行く経路なので、求める答えは$y_{H0}$になります。

普通に行列の掛け算を1回やるのに$O(R^3)$かかりますが、行列の累乗を繰り返し二乗法で行うことで、$O(R^3\log H)$で求めることができ、これなら間に合いそうです。

次に、この行列$A$を求める方法ですが、巡回セールスマン問題(TSP)のようにbitDPで求めることができます。

一般的なTSPはある場所からスタートして、重複なくすべての都市を回って、移動コストが最小となる経路を求める問題ですが、今回は、ある部屋からスタートして、重複なくある部屋に行く経路の組み合わせの数を求めるという問題になります。

同じ部屋は通らないということなので、部分問題としてすでに通った部屋の集合と、今いる部屋と、そこに来るまでの経路の個数がわかっているとします。すると、今いる部屋から行くことができて、まだ通っていない部屋に行くまでの経路の個数に、今いる部屋に来るまでの経路の個数を足していく(配るＤＰ)と次の部屋の経路数が求められます。

漸化式の定義： $$dp[S_i\cup\{u\}][j]=dp[S_i\cup\{u\}][j]+dp[S_i][j]$$

$dp[i][j]$：今部屋$j$にいて、集合$S_i$で表される部屋をすでに通ってきた時の経路の数

$S_i$：すでに通ってきた部屋の番号の集合。

$i$：集合$S_i$の要素(0～15の値)を$i$のビットの位置とみなして、要素に含まれる部屋番号のビットを1とした場合の整数。

$j$：現在いる部屋の番号。

$u$：現在いる部屋$j$から行くことができで、すでに通ってきた部屋に含まれない部屋の番号($g_{j,u}=1\land u\not\in S_iを満たすu$)

$(1\le i \lt 2^R,\ 0\le j\lt R,\ 0\le u\lt R)$

初期値：$dp[\{s\}][s]=1$

求める解：$a_{es}=\displaystyle\sum_{i=1}^{2^R-1}dp[i][e](0\le e\lt R)$

$s$：その階での最初の部屋

$e$：その階での最後の部屋

$u$のループは、$0～R-1$を回して条件が合う時のみ計算します。

$s$を決めてこの漸化式を解くと、$s$から全ての$e$への経路の数が求まります。$s$を全部屋で回すことで、それぞれの部屋から他の部屋への経路の数、行列$A$が求まります。

$i,j,u,s$のループで、$O(2^R\cdot R^3)$になります。

考察

bitDPは、集合$S_i$の要素を整数$i$のビットに割り当てたときに、($S_i$の整数表現)$\lt$($S_i\cup\{u\}$の整数表現)という性質($S_i\subset S_i\cup\{u\}$なので)を使って、ループを$1$から$2^R-1$まで回せばよいというのを理解しておく必要があります。

また、集合の足し算(和集合)や集合にある要素が含まれるかどうかを、ビット演算で実装することも必要です。

集合の足し算(和集合)$S_i\cup\{u\}$：$i\ |\ (1 << u)$

$u\not\in S_i$の真偽：$(i\ \&\ (1 << u)) == 0\ (S_i$に含まれなければ真)

このページのトップヘ