AtCoder Typical DP Contest Q 連結後編 : Grenache's blog

問題概要

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

前編の考察を踏まえて解法を説明していきます。

解法

前編で書いたように、この問題は「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$の最下位ビットが立っている全ての状態を足したものになります。