問題
整数が書かれたマスが一列に個並んでおり最初は全て白く塗られている。連続した
個のマスを黒か白に上書きしていく操作を好きなだけ繰り返して、黒く塗られたマスにある数字の総和を最大化せよ。
答え
1時間かけても解けなかったので解説を読んだ。
操作列を逆順に考えると、ある個の区間を白か黒で決め打ちすれば、他の部分は自由に塗れるということがわかる。よって累積和を使いながら
で計算できる。
考えたことと反省
時系列順に
- 操作が2つある→1つにまとめられないか
一瞬、符号反転みたいな形で2つの操作をまとめられる気がしたけど幻想だった。
- 操作を後ろから考える
これは良い着想だったんだけど、最終状態から考えたため上手くいかなかった。色が未確定という状態を想定することができなかった。一度全部黒く塗った状態から白を上手く塗っていくというようなことも考えたが、そう単純な話ではない。
- (
に対して
が十分大きいとき)端が正ならそれは黒く塗れる
問題の性質として重要な考察の一つ。しかし端だけではなくて、最後に塗る部分以外なら大丈夫というところには気づかなかった。結果的には端付近だけを決め打ってしまうだけにとどまった。
- 左右から2回見る
上の考察を発展させて、左端から確定させていき最後に右端の個を上手く条件に合わせながら最大化するのと、同じことを右端から行い、それらの最大値を返すというのが提出した解答。しかしWAであり、後半が全滅というWAの出方なのでアルゴリズム自体が間違っていそうだという印象は受けた。それにコードも136行という長いものになっていて、感覚的にもこれが想定解だという気はしなかった。
操作列を後ろから考えることや、上手く塗ればかなりの範囲は自由に塗れることには気づいていたのにそれらを上手く組み合わせることができていなかった。コード量、実装法などに違和感を覚えていながら書き始めてしまったが、もっとそこで考察を深めるべきだった。
