かしのブログ

競技プログラミングとか

Typical DP Contest Q - 連結

AtCoder DP

問題

0、1でできた文字列 $w_1, \cdots, w_N$ を連結してできる長さ $L$ の文字列のパターン数を求める。同じ文字列を何度使ってもよい。

考察

NFAを用いた問題の変換

文字列 $w$ の長さの最大値を $|W|$ とし、次のような非決定性有限オートマトン $\mathcal{A}$ を考える。

状態 $S \cdots$ ${S_0} \cup \bigcup_{k=1}^{|W|-1}$ {末尾 $k$ 文字を示す $2^k$ 状態 $S_{k, X}$ }
入力 $\Sigma \cdots$ {0,1}
開始状態 $s_0 \cdots S_0$
終了状態 $A \cdots$ { $S_0$ }
遷移関数 $T \cdots$ {状態 $S_{k, X}$ から、入力 $z =$ 0/1を受け取って、状態 $S_{k+1, Xz}$ への遷移} $\cup$ {文字列 $w$ のある要素を表す状態から $S_0$ へのイプシロン遷移}

文字列 $w$ の長さの最大値が3であり、 $w$ = {0, 01, 10, 100}のとき、 $\mathcal{A}$ はつぎのようになる。

f:id:tnyo43:20200418201225p:plain — q_nfa

◎は $S_0$ 、青/緑の矢印はそれぞれ0/1が入力されたとき、オレンジの矢印は上からそれぞれ0, 01, 100, 10に対応する遷移を表す。

この問題は、「開始状態からL文字入力後に受理状態に戻ってくる文字列のパターン数を求める」問題に帰着できた。

DFAを用いた問題の変換

NFAでは状態の遷移するパターンが多すぎて、パターンを重複なしに数え上げるのは難しい。たとえば、 $\mathcal{A}$ に入力100を与えると

状態100
状態0
状態 $s_0$

のいずれかに遷移している。これらを独立に考えると、10|0と100をうまく区別できない。

そこで、「受理状態に遷移したとみなせる区切り」を保持しながら遷移を繰り返すようにする。1001という文字列を次のように受理状態に遷移したとみなせる区切りの状態を保持しながら遷移させる。

|

-> |1

-> |10| （1->10-> $s_0$ ）

-> |10|0|（(左側の区切りから)1->10-> 100 -> $s_0$ 、(中央の区切りから)0-> $s_0$ ）

-> 0|0|1|（(左側の区切りから)0->01-> $s_0$ 、(中央の区切りから)1-> $s_0$ ）

-> ...

また、初期状態を00...0|とみなすことで、次のような決定性オートマトン $\mathcal{A}^\prime$ で表現できるようになる。

状態 $S \cdots$ ${S_0} \cup \bigcup_{k=1}^{|W|-1}$ {末尾 $k$ 文字とその区切り位置 $2^{k+1}$ を示す $2^{2k+1}$ 状態}
入力 $\Sigma \cdots$ {0,1}
開始状態 $s_0 \cdots$ 00...0|
終了状態 $A \cdots$ {末尾に区切り位置がある $2^{2k}$ 状態}
遷移関数 $T \cdots$ {ある状態の末尾に0/1を追加し、区切り可能な文字列が存在すれば末尾に区切りを追加した状態}

状態数が多くなるので、2文字入力したときに遷移する状態だけ表示した図は次のようになる。

f:id:tnyo43:20200418201227p:plain — q_dfa

たとえば、状態00|0|に0を追加すると、最後の区切りから初めて0という文字列とみなせるので、0|0|0|とする。また、1を追加すると、最後から2文字目の区切りから初めて01とみなせるので0|0|1|とする。一方、たとえば|1|11|に1を追加すると、どこから初めても一致する文字列を作れないので、|11|1に遷移する。また、このときに受理できるのは末尾に区切りがある3つだけである。

$L$ 回遷移したあとに、文字列の最後で区切れるような文字列は受理されるので、これらの状態でのパターンの合計が解になる。

DPに落とし込む

DFAの状態遷移をDPの状態遷移に落とし込む。

${\rm dp}[i$ ] $[s$ ] $[d$ ] $\triangleq$ $i$ 文字目まで見て末尾の状態が（文字列 $s$ 、区切り $d$ ）の文字列のパターン

とする。末尾に文字 $c$ を追加するときは、 $s^\prime \leftarrow s + c, d^\prime \leftarrow (ある区切りから始める文字列があるなら1, ないなら0を追加)$ とした状態 ${\rm dp}[i+1$ ] $[s^\prime$ ] $[d^\prime$ ]に配るDPをする。

遷移をDFAで行うので重複していないことも示すことができる。

計算量は、 $\mathcal{O}(L \cdot |W| \cdot 2^{2|W|} + N \cdot |W|)$

実装

感想

他の人のコードと解説読んでようやく理解できた。理解するのにも時間かかったしバグ取りにも時間かかったから、それぞれもう少し効率よくできるようにしたい。