D. Flood Fill 〜最大回文長とLCS〜

Quiz

https://codeforces.com/contest/1114/problem/D

AC Code

解説

1 2 3 4 5
  • を考えてみる
  • この場合はどこから始めても、4回の塗りが必要。一般に、N-1回塗れば同色にできる
1 2 3 2 1
  • を考えてみる
  • 3を選ぶと、2回の塗りで済む。これは、connected componentの左右が同色で、一気に塗りを広められたため(お得)

圧縮

  • ところで、
1 2 3 3 3 4 5

1 2 3 4 5
  • のように、同じ数字が連続したら圧縮して問題ない
  • 圧縮した配列をAとする

最大回文長

  • 回文の中央から始めればお得が多い
  • 回文は長いほうがいい
  • どう求める?配列A, それをreverseした配列B、それらのLCSが最大回文長
1 2 3 2 1
  • この場合、最大回文長は5
  • お得は2
  • これらの関係は、お得=最大回文長/2
  • デフォルトの塗り回数 N-1
  • 答え
    • N-1 - お得
    • N-1 - LCS/2

計算量

おまけ