あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度６ JOI国のお散歩事情

競プロ

問題原文

問題要旨

一直線上に伸びる数直線上に、 $N$ 人の人がいる。 $i$ 番目の人の位置は $a_i$ である。
人は始め右か左を向いており、１秒にあたり距離１だけ移動する。ただし他の人と出会った場合にはその場で停止する。
$T$ 秒後の、 $x_1$ 番目、 $x_2$ 番目という形で与えられる、 $Q$ 人分の人の位置をそれぞれ求めよ。

$1 \leq N \leq 10^{5}$
$1 \leq T \leq 10^{18}$
$1 \leq Q \leq 1000$
$-10^{18} \leq a_i \leq 10^{18}$
最初人がどちらを向いているのかは $d_i$ という形で与えられる。（1: 右, 2: 左）
$a_i$ は偶数

解法

最初の向きが 12 となっている二人がまずぶつかり、以後溜まり場となって人が流れ込むイメージ。
そのような場所を求めてソートしておけば、二分探索でどの溜まり場で止まるのかを高速に求められる。
$T$ 秒後に溜まり場にたどり着けないことがあるのと、最初どちらを向いているかで少し計算の方法が変わるので注意。

実装

番兵をおいておくと実装が少し楽です。

from bisect import bisect_left
N, T, Q = map(int, input().split())
A, D = [], ''  # d: 1→東, 2→西
for _ in range(N):
    a, d = input().split()
    A.append(int(a))
    D += d
X = [int(input()) - 1 for _ in range(Q)]


batting = [-float('inf'), float('inf')]
for i in range(N - 1):
    if D[i: i + 2] == '12':
        batting.append(A[i] + (A[i + 1] - A[i]) // 2)
batting.sort()


for x in X:
    a, d = A[x], D[x]
    i = bisect_left(batting, a)

    if d == '2':
        i -= 1
        a -= T
        print(max(a, batting[i]))
    else:
        a += T
        print(min(a, batting[i]))

感想

たのしい。こういうのすき。