naoya_t@hatenablog

いわゆるチラシノウラであります

CSAcademy Round #86 (Div. 2 only) C - Palindrome Free Strings

agwたんに聞いた昨夜のCSAのC問題を見てみた

C - Palindrome Free Strings

https://csacademy.com/contest/round-86/task/palindrome-free-strings/statement/
文字列sが与えられて、sがpalindromeな部分を一切含まないようにするには最低何文字変更すればよいか、という問題。

  • 同じ文字のペアはpalindromeを構成する可能性がある
    • その文字の間がpalindromeだったらpalindrome
    • 間に同じ文字が出現していたら…また別の可能性を考えないと?
    • うーん
  • すべてのpalindromeは長さが偶数か奇数
    • 偶数なら abccba のような形
    • 奇数なら abcba のような形
    • ccとかbcbのところを崩せばよいのでは?
      • 崩す過程で他の部分にpalindromeを生じてしまわないか?
      • 近傍で使われていない文字に交換すれば良いのでは?(aabc -> axbc, abacd -> abxcd, aaabc -> axybc のように)
    • aa形、a_a形(_の部分には任意の1文字が入る)をそうやって崩していけばいい
      • 2つ目のaを近傍にない文字に替える。この問題では交換回数だけが問われているので具体的になにを選ぶかは考えなくていい
        • aaaの場合は?2つ目3つ目を近傍にない別々の文字に替えれば良い
    • 左から走査で行けるでしょ。O(N)


ACWA(1)
これだと大きくスキップしちゃっててダメだ
適当な値に替えながら1つずつインクリメント…

→AC

整理

  • palindromeには中心がある
    • 偶数長のpalindromeなら文字と文字の間(ab|ba)、奇数長なら真ん中の文字(ab[c]ba)
  • そういうすべての中心になりうる点の左右(1文字ずつ)を見て、対称でなければいい
    • 中心部分の2文字(ないし3文字)が対称でなければ、その前後に何がついていようがpalindromeではない
    • 他の位置が中心になるpalindromeについては他で検査済み(ないし後で見る)
    • 対称になってしまっているなら近傍で使われていない別の文字に替えることで崩せる


後述のBenq解に似てきた

1位のBenqさんの解法

https://csacademy.com/submission/1727743/
とてもシンプル。左から走査しながら、1つ前2つ前を振り返って比較している。

類題(?)

この問題はa〜zの26文字のアルファベットだから「近傍で使われていない別の文字」とか気軽に言ってるけど、abcの3文字しか使っちゃいけないと言われたら?

→abcabcabc... みたいな繰り返し(6通りあるね)のどれかに帰結しそうだから全6通りそれぞれとの編集距離(※replaceのみ)の最小値が答え、になるのかな?