Quiz
https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b
Submit
https://atcoder.jp/contests/bitflyer2018-final-open/submissions/4881138
解法
- editorialの通り
感想
- lower_boundでiteratorを取ってきた後、+1, -1をしたり、配列の先頭・終端 begin(), end()と比較したりして場合分けをしたりしたが、なかなかうまく行かなかった。ローカルテストでは通るものの、場当たり的対応になって提出後にWAになる。
対策１「累積和の定義を変える」
- 私が今まで使っていた累積和は一般的ではなかったかもしれない。累積和をAc, 配列をAとして
Ac[0] = A[0] Ac[1] = Ac[0] + A[1] ...
- としていた。これはAcのサイズがNで同じになるのが好みであった
- しかし今回からは、A[0] = 0である累積和の方式に変更した。参考：http://drken1215.hatenablog.com/entry/2018/07/01/133700
- こうすると累積和の配列サイズはN+1となってしまうがA[-1]に間違ってアクセスしてしまうことがなくなる
対策２「場合分けを避ける」
- 解説を見てしまっているから分かるのだが、複雑な場合分けは必要ない。不要なのに場合分けをするとバグが入り込みやすい
対策３「図を描く」
- 添付画像のように図を書いて、添字のミスを出さないようにする
Notebook
その他
- この問題はこのバチャコンで解いた。https://not-522.appspot.com/contest/6433587771473920
- レート1200-1600用に突入したが、真ん中より下
- 「競技プログラミングの盛り上がり」を感じる。私が強くなるまでもう少し後でいいのだが・・・
