CROC 2016 - Elimination Round E. Intellectual Inquiry

k 種類のアルファベットで構成された長さ n の文字列を t の末尾に繋げて文字列 s を作る。不連続を許した s の部分文字列の種類数を最大化したい。

s の部分文字列の種類数の最大値を求めよ。

という 2 段階で解く。まずは s の構成から説明する。

t が "abcab" だったとする。

これを n 回繰り返した文字列が最も多くの部分文字列を持つ。証明はしていないが手元の実験では最大値が得られたので多分成り立つ。

s の部分文字列の種類数を求めるには次のような DP をする。

更新は末尾 n-1 から先頭 0 に向かって行う。

"aab" という文字列があったとき、s[0]s[2] と s[1]s[2] が等しいが、なるべく現れるのが早い方の a を使うというルールを採用することでこのような二重カウントを回避できる。つまり j->s[i] の遷移を必ず行えばいい。

手元で作った最大ケースがほぼ 2 sec だったので投げたけどジャッジ側でも 1185 ms 掛かってるので怖い。