第８回日本情報オリンピック 本選（過去問）B - ピザの勉強

atcoder 二分探索

atcoder.jp

この問題は二分探索を使って解けます。コードはpythonでライブラリのbisectを使って書きました。

・プログラムの流れ：店舗の位置に本店の位置(0とD)を加えた。その後、配達先の位置を二分探索して近い店舗2つのうち近い方からの距離をdとした。あとはansにdを加算すれば良い。

・間違ったところ：d=min(abs(DN[bi]-k),abs(k-DN[bi-1]))の部分をabsを書かずにWAしてしまった。出力が負になっていたのでabsをつけたらACした。

・実装例

D=int(input())  #円周の長さ
N=int(input())  #店舗の個数
M=int(input())  #注文の個数

DN=[0]  #店舗の位置
for _ in range(N-1):
    DN.append(int(input()))
DN.append(D)  #本店の位置
DN.sort()
#print(DN)

KM=[]  #配達先の位置
for _ in range(M):
    KM.append(int(input()))
#print(KM)


import bisect
ans=0
for k in KM:
    bi=bisect.bisect_left(DN,k)
    d=min(abs(DN[bi]-k),abs(k-DN[bi-1])) #近い店舗2つのうち近い方からの距離
    #print(k,bi,d)
    ans+=d
print(ans)