問題概要

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

「AtCoder Typical DP Contest Q 連結」を考えているときに参考になった問題です。この問題の解説で書いているのと同じような解法が使えます。

解法

「Q 連結」の解説で書いたように、この問題を下記と同じ考え方で解いていきます。

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

まずは問題を「";"と"_"からなる長さ$L$の文字列において、すべてが";_+;"の部分列に分解できる組合せの数を求めよ。」と言い換えてみます。(厳密な定義ではありませんがざっくりとしたイメージ。"_+"は1個以上の"_"が当てはまるとします。)

この条件を判定するために必要なすべての状態についてですが、1文字ずつ文字を増やしていったときに、部分列は";"だけ、";_+"、";_+;"と状態が変化をしていきます。これらの個数をカウントすることで全体の状態を管理していきます。

1. ";"だけ(他の文字と組み合わさっていない)が$j$個ある状態
2. ";_+"(1個以上の"_"と組み合わさった";")が$k$個ある状態
3. ";_+;"(最終的な形の組み合わせ)が$l$個ある状態

ここで、3.の状態は個数を考える必要はなく、1.の";"だけが0個、2.の";_+"が0個であれば、";_+;"だけができたとみなすことができます。従って状態の遷移は以下のようになります。

• $i+1$文字目が";"なら、新たな部分列の左端の候補と考え、1.の個数が1個増える状態に遷移する($j$個から$j+1$個へ)。
• $i+1$文字目が";"なら、部分列";_+"とつなげて最終形になると考え、2.の個数がが1減る状態に遷移する($k$から$k-1$へ)。その際に、どの部分列";_+"につなげるかという$k$個の候補が存在する(組み合わせ数は$k$倍になる)。
• $i+1$文字目が"_"なら、部分列";"とつなげて部分列";_"になると考え、1.の個数が1減って、2.の個数が1個増える状態に遷移する($j,k$から$j-1,k+1$へ)。その際にどの部分列";"とつなげるかという$j$個の候補が存在する(組合せ数は$j$倍になる)。
• $i+1$文字目が"_"なら、部分列";_+"の"_"の個数が増えると考えて、2.の"_"が増えるだけで状態は変わらない($j,k$から$j,k$へ)。しかし、どの部分列";_+"の"_"の個数が増えるかという$k$個の候補が存在する(組み合わせ数は$k$倍になる)。

このように、「Q 連結」と違って、$i+1$文字目で考えられるすべての状態("0"または"1"を足す)を調べるのではなく、与えられた文字列によって状態の遷移先が決まっていきます。

求める解は$L$文字目ですべての部分列が";_+;"になっていなければいけないので、$j=0,k=0$のときの組み合わせの数になります。

例えば最初の文字が"_"であった場合は、絶対に条件は満たせない(答えは0)のですが、この漸化式で計算すると初期値の$dp[0][0][0]=1$が1文字目の時点で消えてしまいます。$dp[1][0]0]=dp[0][0][0]\cdot 0$となり$i=1$のすべての要素が$0$なので、その後の計算はすべて$0$です。最後に"_"が来た場合も絶対に条件は満たせませんが、この場合も最後に$dp[L][0][0]$に遷移してくる漸化式が、$dp[L][0][0]=dp[L-1][0][0]\cdot 0$なので、同じく答えは$0$になります。

考察

全ての状態をどのように表すのかを考えるのは難しいですが、考え方としてはよく使われるのではないでしょうか。

問題概要

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

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

解法

前編で書いたように、この問題は「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'$を決定します。

この漸化式では$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$文字目で条件に合う状態の値をすべて足したもの。

なんとかＤＰに慣れたい。。。

問題概要

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

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

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

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

解法

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

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

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

• $i$文字目が"0"のとき、$i+1$文字目が"0"および"1"に遷移できる。
• $i$文字目が"1"のとき、$i+1$文字目が"0"および"1"に遷移できる。

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

この漸化式の意味は

• $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)$になります。