7K12 blog

猫でも分かるアルゴリズム解説

第8回日本情報オリンピック 本選 B - ピザ

f:id:tkr987:20200708025631p:plain

f:id:tkr987:20200708025650p:plain

https://atcoder.jp/contests/joi2009ho/submissions/14908294

  • 左回りと右回りの両方を二分探索する
  • 左回りは upper_bound 右回りは upper_bound をデクリメントすると得られる
  • 円環はデータを余分に増やすと実装が楽になることが多い

f:id:tkr987:20200708031253p:plain

制約から二分探索で処理すれば良いが、円環なので左回りと右回り両方で最短を調べる必要がある。左回りのとき最初に到達する店舗が本店となる特殊ケースが存在するので、本店位置として0とdの両方を登録しておくと実装が楽になる。

計算量は O(m \log n)になる。