ABC119 D - Lazy Faith

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, Q = il()
    J = [-MAX] + [ii() for _ in range(A)] + [MAX]
    T = [-MAX] + [ii() for _ in range(B)] + [MAX]
    que = [ii() for _ in range(Q)]
    for q in que:
        a = bisect.bisect_left(J, q)
        b = bisect.bisect_left(T, q)
        ret = MAX
        for j in J[a - 1:a + 1]:
            for t in T[b - 1:b + 1]:
                ret = min(ret, abs(j - q) + abs(t - j), abs(t - q) + abs(j - t))
        print(ret)


if __name__ == '__main__':
    main()

考え方

二分探索(bisect)を使用して、問(q)の位置が
神社の並び(J)と寺の並び(T)において何番目か求める。
求めた位置から前後の神社と寺を対象に、
神社→寺に行くパターンと寺→神社に行くパターンの最短距離を調べる。

注意すべき点は神社の並び(J)と寺の並び(T)に
無限大に小さな位置([-MAX])と無限大に大きな位置([MAX])を追加しておくこと。
(MAX = float('inf'))
これを忘れると問(q)の位置から前後の神社と寺の位置を取得するとき、
リストの範囲外を選択してしまう場合がある。