経緯
竹DP と俗に言われる桁DPの実装テクを知り、桁DPとの解ける問題集合の差異があるのではないかと考えていた所、桁DP が想定解でないものも後に述べる非決定性桁DPを使用する事で解けることに気がついたので記事にしました。
桁DPの軽い解説も書きますが、解説用の記事ではないのでご承知おきください。
わからない事や指摘などはtwitter(@hotmanww) またはQiita の編集リクエストに送ってください。
桁DPとは
競プロテクニックです。ググると無限に解説記事が出てくると思います。
かっこいい感じに言うと。
- DFA(決定性有限オートマトン) が受容する文字列の数はノード数を $N$ として、$\mathcal{O}(N)$ で求められる事 (正確には非輪状)
- $N$ 以下の正整数を受容する ノード数 $\mathcal{O}(\log (N))$ のDFAが存在すること
を用いた数え上げのテクニックです。
競技プログラミングにおけるDFA
DFAはノードと受け取る文字が同じであるならば遷移先が一意に定まる物です。
競技プログラミングでは
- $N$ 以下の正整数を受容するDFA (桁DP:ノード数 $\mathcal{O}(\log N)$)
- 文字列 $S$ の連続部分列全体を受容するDFA (suffix automaton:ノード数 $\mathcal{O}(|S|)$)
- 文字列 $S$ の連続とは限らない部分列を受容するDFA (部分列DP:ノード数 $\mathcal{O}(|S|)$)
- 文字列 $S$ を連続とは限らない部分列として含む文字列全体を受容するDFA (名前募集中: ノード数 $\mathcal{O}(|S|)$)
- 文字列 $S$ を連続部分列として含む文字列全体を受容するDFA (KMP法+$\alpha$/Aho–Corasick algorithm: ノード数 $\mathcal{O}(|S|)$)
あたりが有名です。
- $N$ 文字以下の文字列を受容するDFA (ノード数: $\mathcal{O}(N)$)
- $D$ の倍数を受容するDFA (ノード数: $\mathcal{O}(D)$ )
- 1が連続しない01文字列のDFA (ノード数: $\mathcal{O}(1)$)
等の基本的な物もDFA として覚えておくと(オートマトンの直積を考えることで)考察の助けになるかもしれません。
DFA の苦手なこと
DFA は遷移先が一つなので、「一つの文字列に対して複数の操作が考えられて、そのどれかが受容されるものを数え上げる」といった物を考えるのは難しいです。
そこで NFA(非決定性有限オートマトン)というものを考えます。
具体的には「ノードと受け取る文字が同じであっても遷移先が一つには限らず、適切に遷移先を選べば受容されるノードに到達するならばその文字列は受容されると考える」というものです。
勘がいい人なら気がつくと思いますが、到達しうるノードの集合を管理するDP(bit DP) を考える事で、ノード数 $N$ のNFAは、ノード数 $\mathcal{O}(2^N)$ のDFAに置き換える事ができます。(関連記事(knshnbさんのblog))
非決定性桁DP
よって $N$ 以下の正整数に対する非決定的なDPが $\mathcal{O}(N)$ で出来ました...では殆ど嬉しくないですよね。
実は桁DPの様なものはNFAで考えてもノード数のオーダーが変わらず $\mathcal{O}(\log N)$ のままです(桁数を定数と考えるならば)。
これは、桁DP において、 1 回遷移後のノードと 2 回遷移後のノードが同時に到達しうる事はありえないので、同じ桁のノードは定数個しかないことから、NFAにおいても同じ桁のノードは定数個しか無いことから言えます。
これによって、単純な DFA では受容されるかどうかがわからないものに対しても桁DPを考えることが出来るようになりました。
これによって解ける問題(ネタバレ注意)
(cp-unspoiler はkimiyuki さんによって作成されたネタバレを防ぎつつ問題のリンクを貼るためのサイトです)
想定解は桁DPではないです
$N$ 以下の正整数の集合に対するNFAと考えられるので、集合の集合を管理するDFAに帰着されます。ヒント
探せば他にもあるような気もするので、知ってる方などいれば twitter(@hotmanww) まで連絡ください。
追記
noshi91さんに桁DPの有名題を非決定性桁DPで解いて頂いたやつです
とても機械的に解けるようになっていて分かりやすいので是非参考にしてみて下さい！！
(u, v) を {0, 1}^2 をアルファベットとする文字列と解釈する。twitterリンク(Atcoderの問題へのリンクあり)
・u <= N, v <= N はいつもの DFA で表現できる
・a xor b = u, a + b = v となる (a, b) の存在は NFA で表現できる
後者を powerset construction で DFA に変換して、前者との intersection を取って、受理される文字列の数え上げ