競プロ初中級者100問

JOI2009本選B ピザ

はじめに

カテゴリー競プロ初中級者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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
d = int(input())
N = int(input())
M = int(input())
shop = [0]
home = []
for n in range(N-1):
    shop.append(int(input()))
for m in range(M):
    home.append(int(input()))
shop.sort()
shop.append(d)
ans = 0
for h in home:
    i = bisect.bisect(shop, h)
    ans += min(abs(shop[i-1]-h), abs(shop[i]-h))
print (ans)

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日