概要

数直線上の \(N\) 人の友人全員が立入禁止地点を越えずに到達できる整数座標 \(T\) を選び、移動コストの合計を最小化する問題。立入禁止地点が数直線を「区間」に分割するため、全員が同じ区間に属するか判定し、その区間内で最適な集合場所を求める。

考察

重要な気づき：立入禁止地点による区間分割

数直線は1次元なので、立入禁止地点を越えて移動することはできません。立入禁止地点 \(B\) をソートすると、数直線は以下の区間に分割されます：

\[(-\infty, B_0),\quad (B_0, B_1),\quad (B_1, B_2),\quad \dots,\quad (B_{M-1}, +\infty)\]

友人 \(A_i\) と目的地 \(T\) の間に立入禁止地点があってはならないので、\(T\) と全ての友人は同じ区間に属していなければなりません。

判定方法

友人 \(A_i\) がどの区間に属するかは、ソート済み配列 \(B\) に対して二分探索で「\(A_i\) より小さい \(B\) の個数」を求めれば区間番号が分かります。全員の区間番号が一致しなければ答えは \(-1\) です。

最適な \(T\) の選び方

全員が同じ区間 \([lo, hi]\)（整数範囲）にいると分かったら、\(\sum |A_i - T|\) を最小化する \(T\) を求めます。

制約なしの場合、\(\sum |A_i - T|\) を最小化する \(T\) は \(A\) の中央値（メディアン） です。偶数個の場合は \(A[N/2-1]\) から \(A[N/2]\) の任意の値が最適です。

この最適値が区間 \([lo, hi]\) に収まればそのまま使い、収まらなければ区間の端にクランプ（制限）します。これは \(\sum |A_i - T|\) が中央値から離れるほど単調増加する凸関数であるためです。

アルゴリズム

1. \(A\) と \(B\) をソートする
2. \(M = 0\) の場合：制約なしなのでメディアンでのコストを計算
3. \(M \geq 1\) の場合：
   • 全友人が同じ区間に属するか二分探索で判定（異なれば \(-1\)）
   • 属する区間の整数範囲 \([lo, hi]\) を求める（\(lo > hi\) なら \(-1\)）
   • メディアン（最適値）を \([lo, hi]\) にクランプして \(T\) を決定
   • \(A\) の累積和を用いてコスト \(\sum |A_i - T|\) を \(O(N)\) で計算

コスト計算の工夫

\(A\) がソート済みで累積和 \(\text{prefix}\) を持てば、\(T\) 以下の要素数を \(p\) として：

\[\text{cost} = T \cdot p - \text{prefix}[p] + (\text{prefix}[N] - \text{prefix}[p]) - T \cdot (N - p)\]

計算量

• 時間計算量: \(O(N \log N + M \log M)\)（ソートが支配的）
• 空間計算量: \(O(N + M)\)

実装のポイント

• 区間の端は 開区間 なので、整数座標としては \(B[seg-1]+1\) から \(B[seg]-1\) が有効範囲。隣接する禁止地点の間隔が 1 の場合 \(lo > hi\) となり、有効な整数が存在しないことに注意。

• メディアンのクランプ：偶数個の場合に最適範囲 \([A[(N-1)/2],\ A[N/2]]\) と \([lo, hi]\) の重なりを考える。

• \(A_i\) に重複があっても問題なく処理できる（ソート・累積和で統一的に扱える）。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        A.append(int(input_data[idx])); idx += 1
    
    B = []
    for i in range(M):
        B.append(int(input_data[idx])); idx += 1
    
    B.sort()
    A.sort()
    
    # All friends must be reachable from T without crossing any forbidden point.
    # This means for every friend A_i, the open interval (min(A_i, T), max(A_i, T)) 
    # must contain no forbidden point. Also T must not be forbidden.
    #
    # So T must be in the same "segment" (between consecutive forbidden points) as ALL friends.
    # 
    # The forbidden points partition the number line into segments:
    # (-inf, B[0]), (B[0], B[1]), ..., (B[M-1], +inf)
    # and also single points that are forbidden are excluded.
    #
    # All friends must lie in the same segment, and T must also lie in that segment.
    # If friends are in different segments, answer is -1.
    
    if M == 0:
        # No forbidden points. T can be any integer. Optimal is median of A.
        median = A[N // 2] if N % 2 == 1 else A[N // 2]
        # Actually for even N, any value between A[N//2-1] and A[N//2] works.
        # We just pick median = A[(N-1)//2] or A[N//2], both give same cost.
        # Let's compute cost at median
        # For minimum sum of absolute deviations, pick median
        # With even N, any point in [A[N//2-1], A[N//2]] is optimal
        median = A[N // 2]  # This works for both odd and even
        total = sum(abs(a - median) for a in A)
        print(total)
        return
    
    # Find which segment each friend is in.
    # Segment for a point x (not in B): 
    #   segment index = number of B values < x = bisect_left(B, x)
    # All friends must have the same segment index.
    
    seg = bisect_left(B, A[0])
    for i in range(1, N):
        if bisect_left(B, A[i]) != seg:
            print(-1)
            return
    
    # All friends are in the same segment.
    # Determine the range of valid T values in this segment.
    # Segment `seg` means: 
    #   if seg == 0: T in (-inf, B[0])
    #   if seg == M: T in (B[M-1], +inf)
    #   else: T in (B[seg-1], B[seg])
    
    # T must be integer and not forbidden (which is guaranteed if in open interval between consecutive B's)
    
    if seg == 0:
        lo = -10**18
        hi = B[0] - 1
    elif seg == M:
        lo = B[M - 1] + 1
        hi = 10**18
    else:
        lo = B[seg - 1] + 1
        hi = B[seg] - 1
    
    if lo > hi:
        # No valid integer in this segment
        print(-1)
        return
    
    # Now find optimal T in [lo, hi] that minimizes sum |A_i - T|.
    # Optimal unconstrained T is the median of A.
    # Since A is sorted, median index is (N-1)//2 for lower median.
    # For even N, any T in [A[N//2-1], A[N//2]] gives minimum.
    # We clamp to [lo, hi].
    
    # Lower and upper median
    lower_med = A[(N - 1) // 2]
    upper_med = A[N // 2]
    
    # The optimal unconstrained range is [lower_med, upper_med].
    # Clamp this range to [lo, hi].
    
    # If the ranges don't overlap, pick the closest endpoint.
    if upper_med < lo:
        T = lo
    elif lower_med > hi:
        T = hi
    else:
        # Overlap: pick any point in the overlap, e.g., clamp lower_med to [lo, hi]
        T = max(lower_med, lo)
        T = min(T, hi)
    
    # Compute cost using prefix sums since A is sorted
    # sum |A_i - T| = T * count_left - sum_left + sum_right - T * count_right
    # where left = A_i <= T, right = A_i > T
    
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    pos = bisect_right(A, T)  # number of elements <= T
    sum_left = prefix[pos]
    sum_right = prefix[N] - prefix[pos]
    cost = T * pos - sum_left + sum_right - T * (N - pos)
    
    print(cost)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。