主食は米

主に競プロ備忘録

AGC 008 B - Contiguous Repainting (400)

解法

解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる.

さて,逆順に見ていったときの最初(つまり元の操作で最後)の操作を固定する. これは2(N-K+1)通りある.
後は実験していって気づく必要があるが,それ以外のマスは自由に変えることができる(外側から1つずつずらして範囲を塗っていけばいい)

なので,これをループを回していけばいい. 1回の計算に数列の範囲の最大値が入っているので累積和を使って高速する.

コード