AGC008 B Contiguous Repainting

所見

与えられた手順で"上書き"というのがあるときは手順を逆順にして一つ一つ確定させていくと見通しが良くなる。かしこい。

問題概要

N個のマスに数列が書かれたものが与えられる。以下の操作を好きなだけ繰り返して、黒く塗られたマスに書かれた数の和を最大化せよ。
操作: 連続するK個のマスを選び、それらすべてを白く塗るか黒く塗る。この時、各マスの色は上書きされる。

取った方針

黒く塗る操作を行ったあと1ズレた区間を白く塗ることで任意の1マスを黒く塗ることができることに気づくも、その時に塗られるKマスは自由にならないことに絶望し終了。
解説を見た後だと塗り終わるときのKマスを白くするか黒くするかで全探索したら普通にACだったのでは、と思う……

正しい方針

"何かを上書きしていく問題"については、操作列を逆順に見て、確定させていく、という問題に変換すると見通しが良くなる。
今回の場合、操作は"連続するK個のマスを選び、それらすべてを白く塗るか黒く塗る。この時、各マスの色は上書きされる。"だが、変換すると以下。
"はじめN個のマスの色は確定されていない。連続するK個のマスを選び、それらすべてを白く塗るか黒く塗る。この時、一度塗られたマスは上書きされない。"
この設定の下で考えると、最初に塗られるK個のマス以外は任意の色に塗ることができる。(始めのK個から順番に左右に1ずらした区間を塗ればよい)
よって、初めのK個を白/黒で全探索し、のこりのN-K個は正の数を黒、負の数を白で塗ってスコアを計算すればよい。
これを愚直に計算するとO(N²)かかってTLEするが、K個の数の和、N-K個の数のうち正の数の和をそれぞれ累積和で計算すればO(N)で計算でき、間に合う。

得られた知見

・上書きを含む手順を繰り返す->手順を逆順に見て確定させる操作に変換
・一定条件(ex: 正の数、偶数 etc)を満たす数の和を高速に求める場合でも累積和を使うことが可能

解くのに必要な要素

・上書きする操作を見たら手順を逆順にしてみるという心
・累積和

周辺調査によって得られた知見

特になし