問題概要

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

この問題は理解するのにとても時間がかかりました。なので、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)$になります。