beet's soil

競プロのことなど

AGC026 E - Synchronized Subsequence

区切った後に辞書順最大だけ考える部分の証明がほしいなあと思ったのでする

問題 E - Synchronized Subsequence
公式解説 https://img.atcoder.jp/agc026/editorial.pdf

以降では公式解説を読んだことを前提とします。

補題を5つ示せばそれを組み合わせることで正当性が示せます。

  1. a型の辞書順最大はabab... の形をしている(公式解説にあるので省略)
  2. b型の辞書順最大はO(N^2)で求められる(公式解説にあるので省略)
  3. 文字列の辞書順最大化は後ろからDPで求められる
  4. a型とsuffixの連結時は区間内の最大値だけ考えればよい
  5. b型とsuffixの連結時は区間内の最大値だけ考えればよい
3

ある文字列と複数のsuffixのうちどれかを連結することを考えると、
辞書順最大になるのは明らかにsuffixの中で最大のものであるはず

4

x < "ab" + x ⇒ "ab" + x < "ab" + ("ab" + x) を繰り返し適用すると言える

5

s,t がともにもう一方のprefixでないとき s < t ⇒ s + x < t + x
累積和が0になるところで区切ったのでprefixにはならない

ある区間内から作れる文字列s,t に対して、sがtのprefix、つまり s + u = t であるとする
このときf(x) をxの累積和とすると、 f(u) = f(t) - f(s) = 0 であるはず (∵ 条件よりf(s) = f(t)=0)
しかし、このときtはuの前後で分割可能である したがって矛盾
よってprefixになることはない

これで示せたはず、抜けや漏れ、破綻があれば教えてください。