yukicoder No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
かなり怪しい記事なのであまり信用しないでください。editorialの論文を読みましょう。
http://yukicoder.me/problems/no/465
解法
やりたいことは長さKのPP型接頭辞がいくつあるかのテーブルを計算することである。 これができれば後はどうにでもなる。
愚直に作る方法としては、paltreeを構築してsuflinkを辿ってS[0..k)の回文接尾辞を列挙していくというものがある。 しかし、これではO(回文の総数)掛かるため間に合わない。bitsetで計算量を落とすことはできるが、N=500000なのでどうせ通らないだろう。
S[0..k)のPP分解が複数あること、paltreeのノードをDPに対応させられないことが計算量を落とすことを難しくしている。 ここまで考察ができると、計算量を落とすためには非自明な性質を組み込む必要があることが予想できる。
実は、S[0..k)が複数のPP分解を持つときというのはどういうときなのかを調べてみると良い性質が見つかる。
まず文字列Xが2通りの回文分解AC,DBを持つとする。
このとき、以下のような現象が起きる。
よって、Xはさらに小さなA',B'を用いてX=A'C'=B’D'と分解できる。これを繰り返せば、最終的にABABAB…がちょうどぴったりXになる。よってXはP型文字列の繰り返しか、PP型文字列の繰り返しで表現できることが分かった。
このことが分かると、テーブルがエラトステネスの篩の要領で構成できることが分かる。
問題になるのは、PP型文字列の判定法である。調べてみると、できるという言及は見つかるのだが、やり方が分からないので怪しげな方法を取った。
- 最長回文接尾辞を持つような分解
- 最長回文接頭辞を持つような分解
の2通りだけ試してPP型かどうかを判定するのだが、なかなか上手くいく。嘘解法としては上等なので採用した。
追記(2016/12/17)：PP型判定に関してはN=100までに反例がないことを確認した（確認用コード）
paltreeだと思って取り掛かったので、この解法に至るのに手間取った。
