ABC119 D - Lazy Faith
備忘録
問題
回答
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
)の位置から前後の神社と寺の位置を取得するとき、
リストの範囲外を選択してしまう場合がある。