Grenache's blog

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

問題概要

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

この問題は理解するのにとても時間がかかりました。なので、2回に分けて書くことにします。前編ではこの問題の理解に参考になるであろう問題の考察、後編で解法を書きます。

なかなか他の方の解説を読んでも理解することができなかったのですが、SRM671 Div1 Easy BearCriesの問題(の解説)を見て、やっと理解が進みました。さらに、yukicoder No.291 黒い文字列も同じような考え方の問題だと思います。タイミングよくこれらの問題に出会えてやっと解くことができました。

参考:SRM671 Div1 Easy BearCriesの解説yukicoder No.291 黒い文字列の解説

解法

この問題は「0と1からなる長さ$L$の文字列のうち、ある条件を満たす文字列の個数を求めよ。」と言い換えることができます。条件は「$N$個の文字列の連結でできるもの」となります。

まず最初に、「0と1からなる長さ$L$の文字列の個数を求めよ。」という、何も条件がない問題を考えてみます。これは単純に$2^L$が答えですが、DPを使って解くこともできます。これを漸化式で表すと次のようになります。

漸化式の定義: $$dp[i+1][0]+=dp[i][0]$$ $$dp[i+1][1]+=dp[i][0]$$ $$dp[i+1][0]+=dp[i][1]$$ $$dp[i+1][1]+=dp[i][1]$$

$dp[i][j]$:$i$文字目までの文字列で、$i$文字目が$j$である文字列の組み合わせの数 $(0\le i\le L,\ j=0,1)$

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

求める解:$dp[L][0]+dp[L][1]$

この配るDPで定義した漸化式の意味は

  • $i$文字目が"0"のとき、$i+1$文字目が"0"および"1"に遷移できる。
  • $i$文字目が"1"のとき、$i+1$文字目が"0"および"1"に遷移できる。
ということを表しています。求める解は、$L$文字目が"0"および"1"のときの組み合わせの数の和です。

つぎに、この問題に条件を追加して、「0と1からなる長さ$L$の文字列のうち、0が2つ連続しない文字列の個数を求めよ。」という問題を考えてみます。これを漸化式で表すと次のようになります。

漸化式の定義: $$dp[i+1][1]+=dp[i][0]$$ $$dp[i+1][0]+=dp[i][1]$$ $$dp[i+1][1]+=dp[i][1]$$ $$dp[i+1][0]+=dp[i][0](ただし、i=0のときだけ)$$

$dp[i][j]$:$i$文字目までの文字列で、$i$文字目が$j$である文字列の組み合わせの数 $(0\le i\le L,\ j=0,1)$

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

求める解:$dp[L][0]+dp[L][1]$

この漸化式の意味は

  • $i$文字目が"0"のとき、$i+1$文字目が"1"のみに遷移できる。
  • $i$文字目が"1"のとき、$i+1$文字目が"0"および"1"に遷移できる。
  • ただし、$i=0$のときは2文字連続しないので、"0"へも遷移できる。
ということを表しています。このように、現在の1文字によってつぎに遷移できる先が制限されてしまうということです。3番目の条件は初期値として$dp[1][0]=1,\ dp[1][1]=1$として$i=1$からループを回すと考えても構いません。

さらにもう一問、もうちょっと複雑な条件を追加して「0と1からなる長さ$L$の文字列のうち、0が3つ連続しない文字列の個数を求めよ。」という問題を考えてみます。これまでと同じように考えると、$i+1$文字目への遷移の際に、$i-1$文字目が"0"、$i$文字目が"0"からは$i+1$文字目が"0"へ遷移できないということを実現できれば解けそうです。つまり、$i$文字目と$i-1$文字目の2文字分の状態を保持しておく必要があります。

漸化式の定義: $$dp[i+1][j'\&mask2]+=dp[i][j](ただし、j'\ne 0 \lor i\lt 2)$$

$dp[i][j]$:$i$文字目までの文字列で、$i-1,\ i$文字目をビットとみなした数が$j$である文字列の組み合わせの数 $(0\le i\le L,\ 0\le j\le 3,\ 0\le j'\le7)$

$j$:$i-1,i$文字目が"00"のとき、これを2進数とみなして$j=0$、"01"のときは$j=1$、"10","11"のときはそれぞれ、$j=2,j=3$となる。

$j'$:$j$に1文字足して遷移できる$j'$。つまり、$j$に"0"または"1"を足して、それをビットとみなした数。

typicalDPQ

$mask2$:$j'$の下位2ビットを取り出すためのもの。$mask2=3$。

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

求める解:$\displaystyle\sum_{j=0}^{3}dp[L][j]$

この漸化式の意味は

  • $i-1,i$文字目が"00"のとき、$i+1$文字目が"1"のみ($i-1,i,i+1$文字目が"001")に遷移できる("000"へは遷移できない)。
  • $i-1,i$文字目が"01"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"010"および"011")に遷移できる。
  • $i-1,i$文字目が"10"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"100"および"101")に遷移できる。
  • $i-1,i$文字目が"11"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"110"および"111")に遷移できる。
  • ただし、$i\lt 2$のときは、3文字連続しないので"0"へも遷移できる。
ということを表しています。$i+2$文字目を考える際には$i-1$文字目の情報は必要ないため、$j'$の下位2ビットを取り出して、DPを更新していきます。

これら3つ問題で共通しているのは、次の点です。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るDPで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

この考え方でQ 連結を解くことができます。つまり、この問題の条件に基づいて考えるべき状態数を決めて、どのような状態の遷移が可能かを考えるということになります。

考察

漸化式を見てもらうと、$i$に関しては$i$から$i+1$への配るDPなので2つの領域があれば十分です。ただ、このケースでは値は使い回せないので毎回初期化が必要になり、あまり意味はないのかもしれません。

3問目の$j'$ですが、$j$も$j'$もループを回して条件が合う時だけ実行するようにしてしまうと無駄が多くなります。$j'$は$j$に"0"または"1"を足したものではなければいけないので、$j$をもとに作るようにします。すると、$O(L\cdot2^2\cdot2)$になります。

問題概要

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

これも組合せの数を考えるのに苦労しました。さらに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}$と同じになります。

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

このページのトップヘ