【競プロ】非決定性桁DPという概念を創造した
経緯
竹 DP と俗に言われる桁 DP の実装テクを知り、桁 DP との解ける問題集合の差異があるのではないかと考えていた所、桁 DP が想定解でないものも後に述べる非決定性桁 DP を使用する事で解けることに気がついたので記事にしました。
桁 DP の軽い解説も書きますが、解説用の記事ではないのでご承知おきください。
わからない事や指摘などはtwitter(@hotmanww) または Qiita の編集リクエストに送ってください。
桁 DP とは
競プロテクニックです。ググると無限に解説記事が出てくると思います。
かっこいい感じに言うと。
- DFA(決定性有限オートマトン) が受容する文字列の数はノード数を
N \mathcal{O}(N) N \mathcal{O}(\log (N))
を用いた数え上げのテクニックです。
競技プログラミングにおける DFA
DFA はノードと受け取る文字が同じであるならば遷移先が一意に定まる物です。
競技プログラミングでは
N \mathcal{O}(\log N) - 文字列
S \mathcal{O}(|S|) - 文字列
S \mathcal{O}(|S|) - 文字列
S \mathcal{O}(|S|) - 文字列
S \alpha \mathcal{O}(|S|)
あたりが有名です。
N \mathcal{O}(N) D \mathcal{O}(D) - 1 が連続しない 01 文字列の DFA (ノード数:
\mathcal{O}(1)
等の基本的な物も DFA として覚えておくと(オートマトンの直積を考えることで)考察の助けになるかもしれません。
DFA の苦手なこと
DFA は遷移先が一つなので、「一つの文字列に対して複数の操作が考えられて、そのどれかが受容されるものを数え上げる」といった物を考えるのは難しいです。
そこで NFA(非決定性有限オートマトン)というものを考えます。
具体的には「ノードと受け取る文字が同じであっても遷移先が一つには限らず、適切に遷移先を選べば受容されるノードに到達するならばその文字列は受容されると考える」というものです。
勘がいい人なら気がつくと思いますが、到達しうるノードの集合を管理する DP(bit DP) を考える事で、ノード数
非決定性桁 DP
よって
実は桁 DP の様なものは NFA で考えてもノード数のオーダーが変わらず
これは、桁 DP において、 1 回遷移後のノードと 2 回遷移後のノードが同時に到達しうる事はありえないので、同じ桁のノードは定数個しかないことから、NFA においても同じ桁のノードは定数個しか無いことから言えます。
これによって、単純な DFA では受容されるかどうかがわからないものに対しても桁 DP を考えることが出来るようになりました。
これによって解ける問題(ネタバレ注意)
(cp-unspoiler はkimiyuki さんによって作成されたネタバレを防ぎつつ問題のリンクを貼るためのサイトです)
想定解は桁 DP ではないです
ヒント
探せば他にもあるような気もするので、知ってる方などいれば twitter(@hotmanww) まで連絡ください。
追記
noshi91 さんに桁 DP の有名題を非決定性桁 DP で解いて頂いたやつです
とても機械的に解けるようになっていて分かりやすいので是非参考にしてみて下さい！！
twitter リンク(Atcoder の問題へのリンクあり)