pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CROC 2016 - Elimination Round E. Intellectual Inquiry

codeforces.com

問題概要

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

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

解法

  1. 部分文字列の種類数が最大になる s を構成する
  2. s の部分文字列の種類数を求める

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


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

  • 末尾から見て一番最後に現れる文字は c なので、c を付加して "abcabc" とする。
  • 末尾から見て一番最後に現れる文字は a なので、a を付加して "abcabca" とする。
  • 末尾から見て一番最後に現れる文字は b なので、b を付加して "abcabcab" とする。

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


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

  • dp[i][j] := i 文字目以降を使って作ることのできる先頭の文字が j の部分文字列の種類数

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

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

CROC 2016 - Elimination Round E. Intellectual Inqu ...

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