Grenache's blog

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

カテゴリ: DP(動的計画法)

問題概要

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

これも組合せの数を考えるのに苦労しました。さらに2重にDPを使う必要もあって理解困難。

解法

木の問題なので部分問題として子の部分木を使うのは常道かと思います。親から見たときに子それぞれを根とした部分木での$j$本のdisjointなパスを書く組み合わせの数がわかっているとします。すると、親から見たときに$K$本のパスを書く組み合わせは、子1の部分木から1本、子2の部分木から1本、子3の部分木から$K-2$本書く組み合わせとか、子2から3本、子3から$K-3$本などの組み合わせを考える必要があります。

言い換えると、いろいろなものがいくつかの袋の中に入っていて、ある袋から$j$個の物を取り出す組合せの数がわかっているとします。どの袋からいくつとってもいいとして、合わせて$K$個の物を取り出す組合せの数を求めるような問題となります。

この組み合わせの数を求めるにはナップサック問題のようなDPが必要になります。$i$番目までの子を使って、$j$本のパスを書く組み合わせの数$dp2[i][j]$は、子$c_i$の部分木で$j$本のパスを書く組み合わせが$path[c_i][j]$とすると、$dp2[i][j]=\displaystyle\sum_{k=0}^{j}dp2[i-1][j-k]\cdot path[c_i][k]$のようになります。

typicalDPP

ここまでは子の部分木でできるパスの組合せのみでしたが、これに親から子に辺を引くことで増えるパスの組み合わせを考慮しなければいけません。「disjointなパス」ということから、親から3つの子に辺があるようなパスは条件に合いません(親を2回通らないと書けないから)。条件に合うパスは、親から見たときに子に対しての辺は0,1,2本のどれかになります。また、子に辺をつなげる際にすでにその子の部分木で、子から孫に対して2本の辺が書いてるパスが含まれる場合は新たなパスにすることができません。このように、パスの組み合わせの中に親から何本の辺が書かれているのかというのを状態として管理しなければいけません。

ということで、子$c_i$の部分木で、その子から孫に対しては$l$本の辺$(l=0,1,2)$が出ているパスを含み、合わせて$j$本のパスを書く組み合わせの数を$path[l][c_i][j]$とします。 この時、先ほどのDPでは$i-1$番目までの子の部分木で書ける組み合わせと$i$番目の子のこの部分木で書ける組み合わせをかけていましたが、親$v$からどのような辺を引くかによって、選べるパスの組合せに制限が付きます。

  1. 親$v$からの辺が0本になる組み合わせ
  2. typicalDPP0
  3. 親$v$からの辺が1本になる組み合わせ
  4. typicalDPP1-1
    typicalDPP1-2
    typicalDPP1-3
  5. 親$v$からの辺が2本の組み合わせ
  6. typicalDPP2-1
    typicalDPP2-2
    typicalDPP2-3
漸化式の定義: $$\begin{eqnarray} dp2[0][i][j] & += & dp2[0][i-1][j-k]\cdot path[0][c_i][k]\\ dp2[1][i][j] & += & dp2[0][i-1][j-k]\cdot path[1][c_i][k]\\ & + & dp2[1][i-1][j-k]\cdot path[*][c_i][k]\\ dp2[1][i][j+1] & += & dp2[0][i-1][j-k]\cdot path[0][c_i][k]\\ dp2[2][i][j] & += & dp2[1][i-1][j-k]\cdot path[0][c_i][k]\\ & + & dp2[2][i-1][j-k]\cdot path[*][c_i][k]\\ dp2[2][i][j-1] & += & dp2[1][i-1][j-k]\cdot path[1][c_i][k]\\ \end{eqnarray}$$

$dp[l][i][j]$:$i$番目までの子の部分木を使って、$j$本のdisjointなパスを書ける組み合わせの数のうち、親$v$からの辺の数が$l$のパスを含んだものの数。

$path[l][c_i][k]$:親$v$から見て子$c_i$を根とする部分木に含まれる$k$本のdisjointなパスを書ける組み合わせの数のうち、子$c_i$からの辺の数が$l$のパスを含んだものの数。$path[*][c_i][k]=path[0][c_i][k]+path[1][c_i][k]+path[2][c_i][k]$を意味する。

$i$:親$v$から見たときにその子$c_1~c_m$の何番目を処理しているのかを表す$(0\le i\le m)$。

$(0\le j\le K+1,\ 0\le k \le j)$。

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

求める解:$path[l][v][j]=dp2[l][m][j]\ (0\le j\le K+1,\ l=0,1,2)$親$v$を根とする部分木に含まれるパスの数がこのDPで求められる。

このように親$v$に関する組み合わせの数を求めるために、その子のDPが済んでいないといけないので、適当な木全体の根を決めてから、子にあたる$c_i$を選択してDPする必要があります。$j$ですが、途中の漸化式で左辺が$j-1$になるところがあるため、$j=K+1$の組合せ数も必要になります。従って、$O(n\cdot K^2)$程度になると思います。$l$のループは展開しているので数えていません。

最終的なこの問題の解としては、木全体の根($root$)について$path[*][root][K]$になります。

さらに$i$のループですが、子のDPを先にやるために木全体の根から再帰のDFSでやってみたところ、多分$n=1000$くらいのケースなのでしょう、1ケースだけJavaではTLEになりました。なので、キューなどを使って先に木全体を走査して、葉の方からやるための順番を作ってからDPを行う必要がありました。

考察

この辺りの問題はコンテストの時間内になんて絶対解ける気がしません。TDPCではお二人の方が解かれていましたけど。。。

問題概要

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

なんというか、こんな発想で問題をシンプルにするんだという問題でした。とても一人では思いつける気がしません。

解法

考え方は、同じ文字が隣り合っている箇所のが新しい種類の文字を追加することでどのように変化するのかをDPで求めるというものです。隣の文字が何かとか、どこで隣り合っているかとかは関係なく、同じ文字が隣り合っている箇所の数だけを気にして、隣り合っている箇所の数が0になるのが答えです。

まず、$freq_1$が$6$、$freq_2$が$1$の例を考えてみます。$a$一種類だけの場合は文字列としてaaaaaaしかないので、同じ文字が隣り合っている箇所は5か所あります。ここに、bという文字列を加えて新たな文字列を作る場合を考えます。このとき、すでにある文字列に新しい文字列を挿入して新たな文字列を生成すると考えると、挿入できる場所はaaaaaaの両端も含めて、7か所(長さ+1)になります。

typicalDPO1

挿入した場所がaとaの間の場合、同じ文字が隣り合っている箇所は1つ減ります。もし、挿入した場所が両端のどちらかだった場合は、同じ文字が隣り合っている箇所は変わらず5のままです。ただ、全体の文字列の長さが1増えるので、次に文字列を挿入できる場所が1つ増えます。

次に、$freq_1$が$6$、$freq_2$が$4$の例を考えてみます。この場合は、bbbbをどういう形で挿入するのかの組み合わせを考えます。

typicalDPO2

これらを挿入した場合に増える同じ文字が隣り合っている箇所の数は、bbbbをいくつに分割するかによって決まります。逆に分割した結果の文字列に関係なく、分割数によってのみ決まるということです。

後は、これらの分割された文字列をすでに同じ文字が隣り合っている箇所に挿入するのか、そうではない場所に挿入するのかによって、最終的に出来上がる文字列で同じ文字が隣り合っている箇所の数を決定することができます。ただし、挿入可能な場所には1つの分割した文字列のみを入れることとしています。

まとめると、長さが$freq[i+1]$の文字列を$k$個に分割すると分割の仕方にかかわらず同じ文字が隣り合っている箇所は$freq[i+1]-k$個になります。

長さが$len[i]$の文字列には$len[i]+1$個の文字列を挿入できる場所があります。

従って、$i$種類目までの文字を使って$j$個の同じ文字が隣り合っている箇所がある長さ$len[i]$の文字列に、$i+1$種類目の文字列を$k(1\le k\le freq[i+1])$個に分割して、そのうち$l(0\le l\le k)$個を同じ文字が隣り合っている場所に入れる(残りは同じ文字が隣り合っていない場所に入れる)ことで、新たにできた文字列に含まれる同じ文字が隣り合っている箇所の数は、$j-l+freq[i+1]-k$個になります。これらの組み合わせを配るDPで計算していきます。

漸化式の定義: $$\begin{eqnarray} & & dp[i+1][j-l+freq[i+1]-k]\\ & & += dp[i][j]\cdot {}_{freq[i+1]-1}\mathrm{C}_{k-1}\cdot {}_{j}\mathrm{C}_{l}\cdot {}_{len[i]+1-j}\mathrm{C}_{k-l} \end{eqnarray}$$

$dp[i][j]$:$i$種類目までの文字を使って同じ文字が隣り合っている箇所が$j$個ある文字列の数

$freq[i]$:$i$種類目の文字の使える個数(問題文の$freq_i$が0の部分は除いて考える)

$len[i]$:$len[0]=freq[0],\ len[i]=len[i-1]+freq[i](i\gt 0)\ $($i$種類目までの文字を使った時の全体の文字列の長さ)

$i$:文字の数が$0$ではない文字の種類。全部で$n$種類とする。($0\le i \lt n$)

$j$:同じ文字が隣り合っている箇所の数(0から全ての文字を使った時の長さ-1が最大値)

$k$:同じ種類の文字を分割する数($1\le k\le freq[i+1]$)

$l$:$k$分割した文字列を同じ文字が隣り合っている箇所に入れる数($0\le l\le k,\ $$l\le j$)

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

求める解:$dp[n-1][0]$

${}_{freq[i+1]-1}\mathrm{C}_{k-1}$:長さが$freq[i+1]$の同じ文字からなる文字列を$k$分割した時の組み合わせの数

${}_{j}\mathrm{C}_{l}$:同じ文字が隣り合っている箇所$j$個のうち、$l$箇所に文字列を入れる場所の組み合わせの数

${}_{len[i]+1-j}\mathrm{C}_{k-l}$:同じ文字が隣り合っていない箇所$len[i]+1-j$個のうち、$k-l$個の文字列を入れる場所の組み合わせの数

明示していない条件として、$j$個の同じ文字が隣り合っている箇所に$l$個の分割した文字列を入れるので、$l\le j$でなければならない、$len[i]+1-j$個の同じ文字が隣り合っていない箇所に$k-l$個の分割した文字列を入れるので、$k-l\le len[i]+1-j$でなければならない、があります。

$i,j,k,l$のループで、$O(n\cdot len[n-1]\cdot 10\cdot 10)$です。

考察

「長さが$freq[i+1]$の同じ文字からなる文字列を$k$分割した時の組み合わせの数」ですが、分割したときに0個になるとだめなので、先に分割数分引いて残ったもの($freq[i+1]-k$)を0個も許して$k$分割すると考えます。0個も許して$k$分割するのは、$k-1$個の仕切りを加えて並べ替えを考えることで計算できます。つまり、${}_{freq[i+1]-k+k-1}\mathrm{C}_{k-1}$です。これは、$k$個の区別された箱に$freq[i+1]-k$個の区別できない球を入れる重複組み合わせ${}_{k}\mathrm{H}_{freq[i+1]-k}$と同じになります。

問題が複雑すぎて、詳しく解説するのがどんどん難しくなってきています。わかりにくいところを指摘していただければ、修正を加えたいと思います。

問題概要

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

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で表してパスカルの三角形でも解けるようです)

問題概要

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

巡回セールスマン問題(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 フィボナッチ

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

このページのトップヘ