perogram

B - 交通費

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になる。

対策1「累積和の定義を変える」

  • 私が今まで使っていた累積和は一般的ではなかったかもしれない。累積和を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]に間違ってアクセスしてしまうことがなくなる

対策2「場合分けを避ける」

  • 解説を見てしまっているから分かるのだが、複雑な場合分けは必要ない。不要なのに場合分けをするとバグが入り込みやすい

対策3「図を描く」

  • 添付画像のように図を書いて、添字のミスを出さないようにする

Notebook

f:id:peroon:20190408015404j:plain

その他

  • この問題はこのバチャコンで解いた。https://not-522.appspot.com/contest/6433587771473920
  • レート1200-1600用に突入したが、真ん中より下
  • 「競技プログラミングの盛り上がり」を感じる。私が強くなるまでもう少し後でいいのだが・・・