Shiraz University Local Contest 2011 B, UVa-12378 : Ball Blasting Game

UVa その他のコンテスト

問題概要

長さL(<10^5)の文字列が与えられる。ある文字を選んで消す。それを消して、左右の文字が一緒ならその文字が繋がっている部分を消し、さらに左右の文字が一緒なら…とする。この繰り返しが最も多く発生したときの回数を求める問題。

考えたこと

  • とりあえずuniqueしても良さそうなのでuniqueして考える。
  • 要するに最長回文？
  • 本当に最長回文だった。Manacherで通した。