CEOI 2016 day2 - Match
解法
まず $ S が良い文字列であるかどうかを判定する。これは stack を持ちつつ、$ i = 1,2, \dotsの順に
top() が$ S_iに等しいならそれを取り除き、そうでないなら$ S_iを push する
ことを行えばよい。
先頭とどの位置をマッチングさせればよいか考える。これが高速にわかれば再帰的に部分列についての問題を解けば良い。
まず、次が成り立つ。
$ S_{l..r}と$ S_{l..k}が良い文字列で$ k < rのとき、$ S_{k..r}も良い文字列である。
これは、$ S_{l..k}まで見た時点で stack が空になることからわかる。
そして、次が成り立つ。
先頭とマッチングするのは、$ S_k = S_0かつ$ S_{k+1..N}が良い文字列であるような最大の$ kである。
$ kが上の条件を満たさなければならないのは明らかである。そのような$ kが二つあるとし、それらを$ k_1 < k_2とおく。
$ S_{k_1+1..N}、$ S_{k_2 + 1..N}は良い文字列であるので、$ S_{0..k_1+1}, S_{k_1+1..k_2+1}も良い文字列である。
これらの事実から、$ k = k_1を選んだ場合のマッチングにおいて、$ i < k_1は変更せず、$ k_1を)に変更し、$ i > k_1をうまくいじることでより小さいマッチングが得られる。
$ \mathrm{prev}_{i, c}を、$ S_{j+1..i}が良い文字列となり、$ S_j = cであるような最大の$ jと定めると、これはメモ化再帰などで計算できる。
よってこの問題を$ O(N\sigma)で解くことができた。
感想
N <= 2000 の時点でむずい