概要

数直線上の \(N\) 人の友人が、立入禁止地点 \(B\) を避けて1つの座標 \(T\) に集まるときの、移動コスト（距離の総和）の最小値を求める問題です。

考察

1. 友人が移動できる範囲の条件

各友人 \(i\) の初期座標 \(A_i\) から目的地 \(T\) まで移動する際、その間（両端を除く）に立入禁止地点があってはなりません。 これは、「すべての友人は、自身が初期状態で存在する『立入禁止地点に挟まれた区間』から外に出ることができない」と言い換えることができます。

したがって、各 \(A_i\) に対して、その左右にある最も近い立入禁止地点をそれぞれ \(L_i, R_i\) とすると、友人 \(i\) が移動できる座標 \(T\) の範囲は以下のようになります。 $\(L_i < T < R_i \iff L_i + 1 \leq T \leq R_i - 1\)$

2. 全員が到達可能な範囲の決定

すべての友人が同じ座標 \(T\) に集まるためには、すべての \(i\) について上記の条件を満たす必要があります。 つまり、求める \(T\) の範囲 \([P, Q]\) は、各友人の移動可能範囲の共通部分となります。 - \(P = \max_{1 \leq i \leq N} (L_i) + 1\) - \(Q = \min_{1 \leq i \leq N} (R_i) - 1\)

もし \(P > Q\) であれば、全員が集まれる座標 \(T\) は存在しないため、答えは \(-1\) となります。

3. コストを最小化する \(T\) の決定

全員が集まれる座標の範囲 \([P, Q]\) が存在するとき、この範囲内で移動コストの総和 \(f(T) = \sum_{i=1}^{N} |A_i - T|\) を最小化する \(T\) を探します。

一般に、絶対値の和 \(f(T)\) は凸関数（下に凸な関数）であり、制約がない場合の最小値は \(A\) の中央値で達成されます。 \(A\) を昇順にソートしたとき、中央値（\(N\) が奇数のときは中央の要素、偶数のときは中央の2要素の間の任意の値）を \(M = A[\lfloor (N-1)/2 \rfloor]\) とします。

凸関数の性質から、範囲 \([P, Q]\) において \(f(T)\) を最小にする \(T\) は、中央値 \(M\) を範囲 \([P, Q]\) に収まるように制限（クリップ）した値になります。 $\(T = \max(P, \min(Q, M))\)$

4. コストの高速な計算

最適な \(T\) が決まったら、コストの総和 \(\sum_{i=1}^{N} |A_i - T|\) を計算します。 愚直に計算すると \(O(N)\) かかりますが、事前に \(A\) をソートして累積和を計算しておくことで、二分探索を用いて \(O(\log N)\) で計算できます。

\(T\) 以下の \(A_i\) の個数を \(k\) とすると、コストは以下のように分解できます。 $\(\sum_{i=1}^{N} |A_i - T| = \sum_{A_i < T} (T - A_i) + \sum_{A_i \geq T} (A_i - T)\)\( これを累積和 \)S\( を用いて整理すると、以下の式で \)O(1)\( で計算可能になります。 \)\(\text{コスト} = T \times (2k - N) + S[N] - 2S[k]\)$

---

アルゴリズム

1. 初期処理:

   • 友人たちの座標 \(A\) を昇順にソートします。
   • 立入禁止地点 \(B\) をソートし、端の処理を簡単にするために左右に十分大きな値（\(-\infty, \infty\)）を番兵として追加します。

2. 移動可能範囲 \([P, Q]\) の算出:

   • 各 \(A_i\) について、二分探索（bisect_left）を用いて、その左右にある立入禁止地点 \(L_i, R_i\) を求めます。
   • \(P = \max(L_i) + 1\)、 \(Q = \min(R_i) - 1\) を更新していきます。
   • ※同じ \(A_i\) について何度も二分探索をしないよう、重複を排除した \(A\) のユニーク値に対して処理を行うことで定数倍の高速化ができます。

3. 実現可能性の判定:

   • \(P > Q\) であれば、到達不可能なため -1 を出力して終了します。

4. 最適な \(T\) の決定とコスト計算:

   • 中央値 \(M = A[(N-1)//2]\) を求め、最適な \(T = \max(P, \min(Q, M))\) を決定します。
   • \(A\) の累積和を構築しておき、二分探索で \(T\) の挿入位置 \(k\) を求め、コストを計算して出力します。

---

計算量

• 時間計算量: \(O(N \log N + M \log M)\)

  • \(A\) のソートに \(O(N \log N)\)
  • \(B\) のソートに \(O(M \log M)\)
  • 各 \(A_i\) に対する \(B\) の二分探索に \(O(N \log M)\)
  • 累積和の構築に \(O(N)\)
  • 最適な \(T\) の決定とコスト計算に \(O(\log N)\)
  • 全体として、ソートと二分探索がボトルネックとなり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N + M)\)

  • ソートされた配列や累積和配列を保持するために、入力サイズに比例したメモリを使用します。

---

実装のポイント

• 番兵の追加: 立入禁止地点の配列 \(B\) の両端に -INF と INF を追加しておくことで、「すべての立入禁止地点より左（または右）に友人がいる」場合でも、境界の判定を特別扱いすることなく一様にとらえることができます。

• 重複排除による高速化: 同じ座標に複数の友人がいる場合、その座標に対する \(L_i, R_i\) の探索は1回で十分です。set を用いて重複を排除してから二分探索を行うことで、無駄な計算を削減しています。

  ソースコード

import sys
from bisect import bisect_left
from itertools import accumulate

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    A = [int(x) for x in input_data[2:2+N]]
    B = [int(x) for x in input_data[2+N:2+N+M]]
    
    A.sort()
    
    INF = 10**15
    B_sorted = [-INF] + sorted(B) + [INF]
    
    L_max = -INF
    R_min = INF
    
    # A の重複を削除して二分探索の回数を減らす
    A_unique = sorted(list(set(A)))
    for a in A_unique:
        idx = bisect_left(B_sorted, a)
        L = B_sorted[idx-1]
        R = B_sorted[idx]
        if L > L_max:
            L_max = L
        if R < R_min:
            R_min = R
            
    P = L_max + 1
    Q = R_min - 1
    
    if P > Q:
        print(-1)
        return
    
    mid_val = A[(N - 1) // 2]
    T = max(P, min(Q, mid_val))
    
    S = [0] + list(accumulate(A))
    
    idx_T = bisect_left(A, T)
    
    ans = T * (2 * idx_T - N) + S[N] - 2 * S[idx_T]
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。