Grenache's blog

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

カテゴリ: AtCoder

問題概要

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

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

解法

まずは下記のような具体的な例を考えます。頂点$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$のループは貰うDPで、$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)と次の部屋の経路数が求められます。

漸化式の定義: $$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$に含まれなければ真)

競技プログラミング初心者の方が動的計画法(DP)を勉強するのにお勧めの問題があります。AtCoderで開かれた「Typical DP Contest(tdpc)」です。2013年8月と結構昔に開催されたのですが、今でもたくさんの方が解いています。

このコンテストは、そもそもが「動的計画法の練習をすることを目的」として開催されて、「出題される問題はすべて(他のコンテストで使用できないほど)典型的なDPの問題です」とあるように、ちゃんと理解してみるとDPに関する典型的なテクニックをたくさん学べるとてもいいコンテストだと思います。ただ、難易度は高くて(TopCoder SRM d2 hard程度のものが多いとのこと)、初心者にとってはハードルが高いです。作者の方が一言ヒントをつぶやかれたり、いろいろな方がブログで解説を書かれていますが、一回読むだけではなかなか理解するのが難しいものが多いです。

そこで、競技プログラミング初心者の人にもわかりやすい解説を目指してこのブログを作成しました。もしわかりにくいところなどがあれば指摘していただけるとありがたいです。

また、自分にとってわかりやすかったと思われる他の方のブログも紹介させていただきます。あくまでも私にとってわかりやすかった記事ですので、そのほかにもいろいろ検索して勉強することをお勧めします。

問題概要解説ブログ
A コンテスト基本的な2次元のDPGrenache
B ゲームゲームの最善手Grenache
kagamizさん
C トーナメント確率Grenache
simeji_tanさん
D サイコロ確率、4次元のDP、素因数分解Grenache
kmjpさん
E 数組合せの数、桁DPGrenache
kmjpさん
tshitaさん
F 準急組合せの数、累積和Grenache
mayokoさん
G 辞書順組合せの数、文字列の部分列Grenache
simeji_tanさん
osakさん
H ナップザックナップサック問題の変形、最大値Grenache
kagamizさん
kmjpさん
I イウィ最大値、文字列Grenache
osakさん
???
J ボール期待値、bitDPGrenache
kagamizさん
K ターゲット最大値、LIS、幾何Grenache
kmjpさん
L 猫和の最大値、累積和Grenache
simeji_tanさん
kmjpさん
M 家組合せの数、巡回セールスマン問題(TSP)、
bitDP、行列累乗
Grenache
simeji_tanさん
N 木組合せの数、逆元、パスカルの三角形Grenache
kmjpさん
simeji_tanさん
O 文字列組合せの数Grenache
simeji_tanさん
hadroriさん
P うなぎ組合せの数、木構造Grenache
osakさん
shifthさん
Q 連結組合せの数、文字列、配るDPGrenache
osakさん
shifthさん
R グラフ
S マス目
T フィボナッチ

まだすべての問題を解けていないのですが、解けたらブログに書きたいと思います。

問題概要

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

苦手なタイプの問題です。

解法

DPは前提だとして考えると、部分問題を設定しないといけません。$i-1$番目までの猫で得られる幸福度の総和がわかっているとします。そこに、$i$番目の猫を加えたときに増える幸福度は、猫$i$がすでにいた猫のうち、どの猫と距離1以内なのかによります。$j$番目の猫までと距離1以内とすると、$j\le i$という条件で、$j,j+1,...,i-1,i$番目までの猫もすべて距離1以内になるはずです(自分自身も含めています)。なので、猫$i$の幸福度は$\displaystyle \sum_{l=j}^{i}f_{i,l}$となり、すでにいた$j~i-1$までの猫の幸福度がそれぞれ猫$i$との仲のよさ分増えるので、結局猫$i$の幸福度の分の2倍、$\displaystyle 2\cdot\sum_{l=j}^{i}f_{i,l}$増えることになります。

ここで出てきた、すでにいる猫の(左側の)どこまで距離1以内なのかという条件を付けて部分問題を考えると、猫$i$は猫$j$までが距離が1以内とすると、猫$i$よりも左にいる猫$i-1$は、必ず、猫$j$かそれよりも左にいる猫まで距離1以内のはずです。

なので、猫$i-1$が$j,j-1,...,1$番目の猫まで距離1以内の時の幸福度の最大値に、$i$番目の猫を加えたときに増える幸福度を足して最大になるような幸福度の総和を求めればよいことになります。

配列でイメージを示すと以下のようになります。

typicalDPL
漸化式の定義: $$dp[i][j]=\begin{cases} \max\{dp[i-1][k]+\sum_{l=j}^{i}f_{i,l}:k=1,2,...,j\} & (j\lt i)\\ \max\{dp[i-1][k]:k=1,2,...,j-1\} & (j=i) \end{cases}$$

$dp[i][j]$:$i$番目までの猫で、猫$i$から猫$j$までが距離1以内のときの幸福度の総和の最大値。($j=i$の時は猫$i$を加えても全体の幸福度は増えないので$i-1$番目までの猫での幸福度の最大値と同じ)

$f_{i,j}$:猫$i$と猫$j$の仲のよさ。

$(1\le i \le n,\ 1\le j\le i)$

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

求める解:$2\cdot dp[n][j]$の最大値$(1\le j\le n)$

漸化式の中で、$k$と$l$は別にループが回せるので、これで$O(n^3)$になり、このままではまだ駄目です。

図の中の1)の部分ですが、$l$を$i$から$j$の方向に累積和を考えることで、$\displaystyle sum[i][j]=\sum_{l=j}^{i}f_{i,l}$という$sum[i][j]$を$O(n^2)$で事前に計算することができます。

図の中の2)の部分ですが、$dp[i][j]$を猫$i$からの距離が1以内の猫が、猫$j$かそれよりも左の場合の幸福度の最大値、つまり上記の漸化式で$dp[i-1][j]=\max\{dp[i-1][k]:k=1,2,...,j\}$と定義しなおすと、$dp[i][j]=\max\{dp[i][j-1], dp[i-1][j]+sum[i][j]\}(j=1,2,...)$と更新していくことで、$k$のループを回す必要がなくなります。

これらを踏まえて漸化式を書き直すと$O(n^2)$で解けます。

漸化式の定義: $$dp[i][j]=\begin{cases} \max\{dp[i][j-1],\ dp[i-1][j]+sum[i][j]\} & (j\lt i)\\ \max\{dp[i][j-1],\ dp[i-1][j-1]\} & (j=i) \end{cases}$$

$dp[i][j]$:$i$番目までの猫で、猫$i$から猫$1$~猫$j$のどれかまでが距離1以内のときの幸福度の総和の最大値。

$sum[i][j]$:猫$i$が猫$j$から自分自身までが距離1以内の時の猫$i$の幸福度。

$(1\le i \le n,\ 1\le j\le i)$

初期値:$dp[1][1]=0$、$dp[i][0]=-INF(1\le i \le n)$(適切な小さな値)

求める解:$2\cdot dp[n][n]$

猫$i$が加わることによって増える全体の幸福度の総和は、猫$i$の幸福度の2倍なのですが、DPの時は2倍せずに最後の解のところで2倍するようにしています。

初期値の$-INF$ですが、最小の仲のよさの最小値が$-1000$、猫が1000匹までなので1匹の幸福度の最小値が$-10^6$、1000匹の総和で$-10^9$までなりそうです。したがって、$-INF$はこれよりも小さい値でなければいけません。

考察

図中の1)の累積和のオーダーを落とすところはわかるような気がするのですが、2)のオーダーの落とし方が結構苦手です。最初解いたとき(解説見た後に)は$O(n^3)$でもACだったのですが、いろいろな解説を見ると$O(n^2)$だということで、この投稿を書く中で何とか理解したつもりです。

このページのトップヘ