はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4
この問題は二分探索を用いて解くことができます。
方針
全探索を行うと計算量はO(mn)
となり、満点にはなりません。そこで探索範囲を絞ります。
宅配先までは、環状線上で隣接する二店舗のうちのどちらかから配達するべきです。これは事前に店舗を位置でソートしておき、クエリ(宅配先)に対して二分探索を行うことで、計算量はO((m+n)logn)
となり間に合います。
円環を扱う際は何らかの工夫をして一次元空間に落とすと良いです。今回であれば、本店が位置0
だけでなく位置d
にも存在するとみなすと良いでしょう。
Python
の場合bisect
を用いるのが良いでしょう。
コード
1 | import bisect |
shop
は必ず本店0
を含んでいるため、bisect.bisect
の結果はi=0
にはなりえず、shop[-1]
への期待しない参照は発生しません。
なおbisect.bisect
ではなくbisect.bisect_left
を使ったとしても、h=0
の時shop[0]
との距離が0
となり最小値となるため、shop[-1]
を参照するものの問題はありません。
記事情報
- 投稿日:2020年5月17日
- 最終更新日:2020年5月17日