AtCoder のAC数と yukicoder のAC数を足し合わせてTop20ランキングを作成しました。ユーザ名はAtCoderのユーザIDになっています。
AtCoderのIDとyukicoderのIDのマッチングで間違いがあったら、ご指摘ください。
AtCoderのAC数はAtCoder Problemsからいただいています。
(Top20に変更。160704)
カテゴリ： AtCoder
AtCoder Typical DP Contest Q 連結 後編
問題概要
問題文はこちらを参照してください。
前編の考察を踏まえて解法を説明していきます。
解法
前編で書いたように、この問題は「0と1からなる長さLの文字列のうち、N個の文字列の連結でできる文字列の個数を求めよ。」と言い換えることができます。これを下記と同じ考え方で解いていきます。
- $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
- $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
- $i$文字目で考えるべき状態数は、問題の条件に依存する。
- 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。
まずは$i$文字目で考えられるすべての状態についてです。ここで持つべき状態は、$i+1$文字目を含めて考えたときにそれが起きうるのかどうかを判定できるだけの情報がなければいけません。連結する文字列の最大長が8文字なので、$i+1$文字を含めて8文字、つまり$i$文字目までで7文字分の状態を持っておく必要があります。
さらに連結する候補の文字列の長さが異なっているので、7文字分のどこに連結点があるのかを持っておく必要があります。7文字の文字列には8か所の連結点候補があるので、8ビットの数で表すことができます。
つぎに、$i+1$文字目のどのような状態に遷移できるのかですが、$i$文字目までの7文字分に1文字足して8文字分の文字列を考えます。この8文字分が、連結候補の文字列で終わることができれば、新たな連結点を右端に設定します。連結候補の文字列で終わることができなければ、右端は連結点ではない状態に遷移します。
このように、$i+1$文字目に"0"または"1"を足して、それぞれ遷移が可能な$j'$と$k'$を決定します。
漸化式の定義：
$$dp[i+1][j'\&mask7][k'\&mask8]+=dp[i][j][k]$$
$dp[i][j][k]$：$i$文字目までの文字列で、$i-6からi$文字目7文字分をビットとみなした数が$j$であり、その数の連結点をビットで表した数が$k$である文字列の組み合わせの数 $(0\le i\le L,\ 0\le j\lt 128,\ 0\le j'\lt 256,\ 0\le k\lt 256,\ 0\le k'\lt 512)$
$j'$：$j$から1文字足して遷移できる$j'$。つまり、$j$に"0"または"1"を足して、それをビットとみなした数。
$k'$：$j'$の連結点を表す。$j'$は$j$に1ビット足したものなので、$k$を1ビット左にシフトしたものになる。もし、$j'$と$k'$から決定される各連結点から最下位ビットまでの文字列が$N$個の文字列に含まれる場合は最下位ビットも連結点になりうる。つまり、$k'$の最下位ビットをたてる。
$mask7$：$j'$から下位7ビットを取り出すためのもの。$mask7=127$
$mask8$：$k'$から下位8ビットを取り出すためのもの。$mask8=255$
初期値：$dp[0][0][1]=1$($k=1$は文字列の先頭が連結点になることを示す)
求める解：$\displaystyle\sum_{j=0}^{127}\sum_{k=0}^{255}dp[L][j][k]$(ただし、$k\&1\ne 0$を満たす$k$)
この漸化式では$i$文字目から遷移できるすべての状態について遷移しています。最終的に答えに関係ないかどうかがこの時点では決定できないからです。つまり、$i+1$文字目で連結点が設定できない文字列でもこの先で使われる可能性があるということです。
また、この漸化式で同じ文字列になる場合を2重にカウントしないことになるのかという点も確認しないといけません。これは$j$の値が同じ場合は連結点が一番多い$k$の値のところのみへ初期値が遷移していくので、すべての状態の遷移を計算しても2重カウントは発生しません。以下2つの具体的なケースについて例を挙げてみます。
なぜ2重カウントされないのかをうまく言葉では表せていませんが、何とかわかっていただけるでしょうか。
この漸化式を実装すると$i,j,k,j',k'$のループが必要となりますが、$j',k'$は全値をループするわけにはいきません。まず、$j'$は$j$に"0"または"1"を追加してできるので$O(2)$です。$k'$は$N$個の文字列の中に$j'$の連結点から見た文字列が含まれるかどうかを調べるために回す必要があります。連結候補の文字列が存在するかどうかを長さとビットパターンのboolean配列(wt[8][256]など)で事前に作っておくことで、各連結点を見る$O(8)$でチェックできます。したがって、全体では$O(L\cdot 128\cdot 256\cdot 2\cdot 8)$になります。
求める解は$L$文字目が連結点になっていなければいけないはずなので、$k$の最下位ビットが立っている全ての状態を足したものになります。
考察
なぜこの方法で解けるのかは分かったつもりですが、この問題が出ても思いつけそうな気は相変わらずしません。。。
ただ、次の考え方は典型の解法として使えると思いました。
- $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
- $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
- $i$文字目で考えるべき状態数は、問題の条件に依存する。
- 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。
なんとかＤＰに慣れたい。。。
AtCoder Typical DP Contest Q 連結 前編
問題概要
問題文はこちらを参照してください。
この問題は理解するのにとても時間がかかりました。なので、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[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]$
この配るＤＰで定義した漸化式の意味は
- $i$文字目が"0"のとき、$i+1$文字目が"0"および"1"に遷移できる。
- $i$文字目が"1"のとき、$i+1$文字目が"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"へも遷移できる。
さらにもう一問、もうちょっと複雑な条件を追加して「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"を足して、それをビットとみなした数。
$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"へも遷移できる。
これら3つ問題で共通しているのは、次の点です。
- $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
- $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
- $i$文字目で考えるべき状態数は、問題の条件に依存する。
- 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。
この考え方でQ 連結を解くことができます。つまり、この問題の条件に基づいて考えるべき状態数を決めて、どのような状態の遷移が可能かを考えるということになります。
考察
漸化式を見てもらうと、$i$に関しては$i$から$i+1$への配るＤＰなので2つの領域があれば十分です。ただ、このケースでは値は使い回せないので毎回初期化が必要になり、あまり意味はないのかもしれません。
3問目の$j'$ですが、$j$も$j'$もループを回して条件が合う時だけ実行するようにしてしまうと無駄が多くなります。$j'$は$j$に"0"または"1"を足したものではなければいけないので、$j$をもとに作るようにします。すると、$O(L\cdot2^2\cdot2)$になります。
AtCoder Typical DP Contest P うなぎ
問題概要
問題文はこちらを参照してください。
これも組合せの数を考えるのに苦労しました。さらに2重にＤＰを使う必要もあって理解困難。
解法
木の問題なので部分問題として子の部分木を使うのは常道かと思います。親から見たときに子それぞれを根とした部分木での$j$本のdisjointなパスを書く組み合わせの数がわかっているとします。すると、親から見たときに$K$本のパスを書く組み合わせは、子1の部分木から1本、子2の部分木から1本、子3の部分木から$K-2$本書く組み合わせとか、子2から3本、子3から$K-3$本などの組み合わせを考える必要があります。
言い換えると、いろいろなものがいくつかの袋の中に入っていて、ある袋から$j$個の物を取り出す組合せの数がわかっているとします。どの袋からいくつとってもいいとして、合わせて$K$個の物を取り出す組合せの数を求めるような問題となります。
この組み合わせの数を求めるにはナップサック問題のようなＤＰが必要になります。$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]$のようになります。
ここまでは子の部分木でできるパスの組合せのみでしたが、これに親から子に辺を引くことで増えるパスの組み合わせを考慮しなければいけません。「disjointなパス」ということから、親から3つの子に辺があるようなパスは条件に合いません(親を2回通らないと書けないから)。条件に合うパスは、親から見たときに子に対しての辺は0,1,2本のどれかになります。また、子に辺をつなげる際にすでにその子の部分木で、子から孫に対して2本の辺が書いてるパスが含まれる場合は新たなパスにすることができません。このように、パスの組み合わせの中に親から何本の辺が書かれているのかというのを状態として管理しなければいけません。
ということで、子$c_i$の部分木で、その子から孫に対しては$l$本の辺$(l=0,1,2)$が出ているパスを含み、合わせて$j$本のパスを書く組み合わせの数を$path[l][c_i][j]$とします。 この時、先ほどのＤＰでは$i-1$番目までの子の部分木で書ける組み合わせと$i$番目の子のこの部分木で書ける組み合わせをかけていましたが、親$v$からどのような辺を引くかによって、選べるパスの組合せに制限が付きます。
- 親$v$からの辺が0本になる組み合わせ
- 親$v$からの辺が1本になる組み合わせ
- 親$v$からの辺が2本の組み合わせ
漸化式の定義：
$$\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$を根とする部分木に含まれるパスの数がこのＤＰで求められる。
このように親$v$に関する組み合わせの数を求めるために、その子のＤＰが済んでいないといけないので、適当な木全体の根を決めてから、子にあたる$c_i$を選択してＤＰする必要があります。$j$ですが、途中の漸化式で左辺が$j-1$になるところがあるため、$j=K+1$の組合せ数も必要になります。従って、$O(n\cdot K^2)$程度になると思います。$l$のループは展開しているので数えていません。
最終的なこの問題の解としては、木全体の根($root$)について$path[*][root][K]$になります。
さらに$i$のループですが、子のＤＰを先にやるために木全体の根から再帰のDFSでやってみたところ、多分$n=1000$くらいのケースなのでしょう、1ケースだけJavaではTLEになりました。なので、キューなどを使って先に木全体を走査して、葉の方からやるための順番を作ってからＤＰを行う必要がありました。
考察
この辺りの問題はコンテストの時間内になんて絶対解ける気がしません。TDPCではお二人の方が解かれていましたけど。。。
AtCoder Typical DP Contest O 文字列
問題概要
問題文はこちらを参照してください。
なんというか、こんな発想で問題をシンプルにするんだという問題でした。とても一人では思いつける気がしません。
解法
考え方は、同じ文字が隣り合っている箇所の数が新しい種類の文字を追加することでどのように変化するのかをＤＰで求めるというものです。隣の文字が何かとか、どこで隣り合っているかとかは関係なく、同じ文字が隣り合っている箇所の数だけを気にして、隣り合っている箇所の数が0になるのが答えです。
まず、$freq_1$が$6$、$freq_2$が$1$の例を考えてみます。$a$一種類だけの場合は文字列としてaaaaaaしかないので、同じ文字が隣り合っている箇所は5か所あります。ここに、bという文字列を加えて新たな文字列を作る場合を考えます。このとき、すでにある文字列に新しい文字列を挿入して新たな文字列を生成すると考えると、挿入できる場所はaaaaaaの両端も含めて、7か所(長さ+1)になります。
挿入した場所がaとaの間の場合、同じ文字が隣り合っている箇所は1つ減ります。もし、挿入した場所が両端のどちらかだった場合は、同じ文字が隣り合っている箇所は変わらず5のままです。ただ、全体の文字列の長さが1増えるので、次に文字列を挿入できる場所が1つ増えます。
次に、$freq_1$が$6$、$freq_2$が$4$の例を考えてみます。この場合は、bbbbをどういう形で挿入するのかの組み合わせを考えます。
これらを挿入した場合に増える同じ文字が隣り合っている箇所の数は、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$個になります。これらの組み合わせを配るＤＰで計算していきます。
漸化式の定義：
$$\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}$と同じになります。
問題が複雑すぎて、詳しく解説するのがどんどん難しくなってきています。わかりにくいところを指摘していただければ、修正を加えたいと思います。
