7/16記録

ABC 095をセルフコンテスト. C問題までさくさく解けたがやはりD問題で詰まりました.
D - Static Sushi
試行錯誤しながら実装し, なんとかサンプルと答えを合わせられたので提出するとぽつぽつとWA. あきらめて解説をちらちら見ると方針はあっていたので, 実装のミスと思ってAtCoder配布のテストケースを取り寄せていろいろと実験. 計算された数値をみると, やはり考察が間違っていたのでそこを修正. 提出するとACできました.
この問題の最適解において, 来た道を戻ることは2回以上ありません. 最終的に食べる寿司の範囲を考えると, 2回以上折り返すときよりも, 移動距離がより短いたどり方で範囲内の寿司をなめることができる方法が存在することから示すことができます. よって, スタート地点から先に時計回りに行き, 戻ってきて半時計回りor逆or戻らないの択を調べればよいです. 実装では様々な工夫をして計算量を落とす必要がありました(累積和など). 片方のルートを全探索して, もう片方のルートの対応する最大カロリーを予め計算しておくことで計算量を落とせます.
提出したもの
Submission #2856875 - AtCoder Beginner Contest 095

ABC102のD問題も解きました.
D - Equal Cut
解説を見て解けなくて放置していましたが, いろいろと忘れていて苦戦しました. 集合を2分割する真ん中の線を引き, さらに分かたれた2つの集合を分ける方法を探索する方針をとりました. 集合を2分割する方法は全探索します. それぞれの集合の和の絶対値が小さくなるように分けたものが解の候補となるので, これを探索しますが愚直にやると間に合いません. 真ん中の線が移動するにつれて, 左右の線も右にずれていくのが直感的にわかるので, しゃくとり法を用いることで$O(n)$で実装できます. 計算量を落とすためというかP,Q,R,S値を計算するために累積和をとっておく必要があります.
Submission #2857282 - AtCoder Beginner Contest 102