AGC 008 B-Contiguous Repainting
いろいろ考えてみたものの, 解法が思いつかず解説を見ました.
B - Contiguous Repainting
この操作において一回以上操作を行うとき, 最後の操作が存在しており, そのときに塗る色は白か黒で, K個の連続した区間を同じ色を塗ることになります. 一回以上操作を行ったときは必ずK個の連続した区間が同じ色で塗られている場所が存在することがわかります. この最後に塗る白か黒の区間を最終区間と呼ぶことにします. では, 最終区間以外の色の塗り方の自由度はどうでしょうか. 最終区間は最後に色を上塗りすれば途中過程はなんでもいいので, 色塗りのワークスペースとして使えます.
ここで, 最終区間をワークスペースとして, 要素全体の右端または左端を含むK個の区間を白または黒で塗り, 左または右に一個ずつずらしていくことで最終区間以外の場所の色はすべて自由に塗れることがわかります. 最終区間の色は白または黒の二通りで, 最終区間の候補をすべて調べればいいことがわかります.
最終区間以外すべて自由に塗れるので, 最終区間以外の0より大きいものをすべて足し, 最終区間を白とするか黒とするか(加えるor加えない)の二択を試せばよいです.
最終区間の候補はN-K+1個あり, それぞれについていちいち合計をためしていると, $O(N^2)$となりますが, 累積和と正の要素のみの累積和の2種の累積和を使うと$O(N)$で求めることができます.
