東京工業大学プログラミングコンテスト2015 P問題 - Dancing stars on regular expession!
regular expession とは……
やったことを書きます。解説ではありません（適当な仮説に基づいているので誰か示すか反例を出すかしてください）。
やること
"*なし正規表現" で表せるのは
- 受理言語が有限
- 受理言語の補集合が有限
のどちらかなので、与えられた "!なし正規表現" がどちらかを満たしているかを判定する。
与えられた "!なし正規表現" の受理言語が有限かどうかは、否定がないので単に * があるかどうかを見ればよい。なので、受理されない語が有限個かどうかを判定するのが本質。
今回はアルファベットが 1 種類なのでありうる語全体を自然数と同一視する。
場合1
まず考えられるのはサンプル 2 にあるような、2n または 2n+1 を受理するので YES というような場合。
こういう感じで受理されない語が有限個になるときは N〜2N は全て受理されるような気がする。なぜなら、入力が N 文字しかない状態で、kn, kn+1, ..., kn+k-1 を受理するようにしておきながら、N 以上の数を受理しないようにするのは無理そう。
逆に N〜2N が全て受理されるときは受理されない語は有限個になりそう。これも仮説だけど、入力が N 文字しかない状態で N〜2N を全部尽くしたのに、2N より大きい数を無限個取りこぼすのは無理そうなので。
この場合を判定するには入力をパースしながら 1〜2N のうちどれが受理されるかを持っておけばよい。愚直にやると (e1;e2) の処理に O(N^2) かかって全体で O(N^3) となってしまうので、(e1;e2) の処理を FFT で O(N log N) でやる。
場合2
N〜2N に穴があっても、受理されない語が有限個になることは十分ありうる。たとえば
(*(aaaa);*(aaaaa))
は 18 文字で 19 を受理しないが、受理されない語は有限個しかない（gcd(4, 5) = 1 なので 20 以上の数はすべて受理される）。
より一般には a1 * n + a2 * m + ... + ak * p を受理するような形で gcd(a1, a2, ..., ak) = 1 のものがあれば、受理されない語は有限個しかないことになる。
そこで、入力の表現の中にどのような周期の * による繰り返しがあったかを調べる。また、サンプルにあるように
(*(aa)+*(aaa))
は無限個の語を受理しない。このように繰り返しどうしが + で繋がれた場合はどちらを選ぶかを選択しないといけないので、周期の長さだけでなく入力の構造のどこにその周期の繰り返しがあるかまでを調べたい。
そこで入力の表現をグラフに落として考える。要は NFA のようなものを考えるが、今回は * の繰り返しとその周期の長さだけに興味があるのでその点を簡略化する。
場合 1 で入力をパースするときに同時にグラフも作ることにする。*(e) が出てきたとき、e が 1〜N のうちどれを受理するかは（場合1 の処理で）分かっているから、そのとき *(e) に対応する頂点を作ってそこに周期の長さをメモしておく（e が 1〜N のうち複数個を受理できるならその GCD をメモすればよい）。なお、e の中に * が出てくる場合、その内側の * に対応する頂点は捨ててしまってよい。
今見ているものが *(e) でないときは NFA と同じように適当に作る。
あとは出てきたグラフ（DAG）上の初期状態から受理状態へ至るパスで、通った *(e) に対応する頂点にメモされている値すべての GCD が 1 になるようなものがあるかを調べればよい。これはなんか爆発しそうな気もするけどそこまで悪質なケースなさそうだと思って適当にやったら通った。これは値が N 以下なので各頂点に至るパスで GCD が k になるかを全部考えても O(N^2) で余裕。
