Quiz
https://codeforces.com/contest/1114/problem/D
AC Code
- https://codeforces.com/contest/1114/submission/56634318
- LCSのvector
versionがある
解説
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
計算量
- LCSの計算量は、配列の長さをm, nとするとO(m * n)なので、今回の場合O(N2), よって間に合う
- O(n logn)解法もあるようだ https://kopricky.github.io/code/ClassicProblem/longest_common_sequence.html
おまけ
- 最長回文 http://www.prefield.com/algorithm/string/manacher.html
- O(N)で求まるようだ