contiguous repainting - agc 008 b

#上書き #逆から #開区間

とりあえずdebug記。解き方はあと。
リンク1のコードはwaのコード。
リンク2のコードはwaのケースを出すコード。1例として、
6 3
0 4 -9 -9 0 -3
で答え4に対し1になる。
変なことやってた。kマス連続白の区間決めて外の区間全部黒にして、決めた白い区間から黒にするの選べると勘違いしてた。白の区間決めたらその区間からは選べず、外の区間から黒にするの選べる。つまり、kマス連続黒のパターンで、外の区間から選べるのは同じで、選んだ連続マスは選べなくなるだけ。

上書き系の問題は逆から見るといいらしい。つまり、ゴールから見る。連続k区間を同じ色で塗る(反転していくのではない)ので、最後は少なくとも1箇所連続k区間が同じ色。その連続k区間の外は自由に色を選べる。なぜなら、一番外側から内側に色決められるから。
あとは開区間に慣れんと速く書けんしストレス続くー。

リンク1、Submission #6764530 - AtCoder Grand Contest 008
リンク2、https://ideone.com/Lwo6Vn
リンク3、AtCoder AGC 008 B - Contiguous Repainting (400 点) - けんちょんの競プロ精進記録