概要

数直線上の \(N\) 人の友人を1つの座標 \(T\) に集めるときの、移動距離の総和の最小値を求める問題です。ただし、立入禁止地点 \(B\) をまたぐ移動や、立入禁止地点に留まることはできません。

考察

1. 立入禁止地点が移動に与える影響

友人のうち最も左にいる人の初期座標を \(A_{\min}\)、最も右にいる人の初期座標を \(A_{\max}\) とします。

もし、開区間 \((A_{\min}, A_{\max})\) の中に立入禁止地点 \(B_j\) が1つでも存在する場合、どのような目的地 \(T\) を選んでも全員が集まることはできません。 - 目的地 \(T\) が \(B_j\) より左（\(T < B_j\)）にある場合、最も右にいる人（\(A_{\max} > B_j\)）は \(B_j\) を越えて左に進むことができません。 - 目的地 \(T\) が \(B_j\) より右（\(T > B_j\)）にある場合、最も左にいる人（\(A_{\min} < B_j\)）は \(B_j\) を越えて右に進むことができません。 - 目的地 \(T\) 自体を \(B_j\) とすることも、立入禁止地点のため不可能です。

したがって、開区間 \((A_{\min}, A_{\max})\) に立入禁止地点が1つでも含まれる場合は、即座に -1 を出力すればよいことが分かります。

2. 立入禁止地点が存在しない場合

開区間 \((A_{\min}, A_{\max})\) に立入禁止地点が1つも含まれない場合を考えます。 このとき、閉区間 \([A_{\min}, A_{\max}]\) の中には立入禁止地点が1つも存在しません（友人の初期座標 \(A_i\) は立入禁止地点ではないことが保証されているため、端点も立入禁止地点ではありません）。

したがって、この区間内の任意の整数座標 \(T\) を目的地として選ぶことができ、すべての友人は立入禁止地点に阻まれることなく \(T\) に到達可能です。

3. コストの最小化

障害物を考慮しない場合、距離の総和 \(\displaystyle\sum_{i=1}^{N} |A_i - T|\) を最小化する \(T\) は \(A\) の中央値（median） であることが数学的に知られています。 \(A\) を昇順にソートしたとき、中央値 \(T = A[N / 2]\) は必ず \([A_{\min}, A_{\max}]\) の範囲内に位置します。

先ほどの考察より、区間 \([A_{\min}, A_{\max}]\) には立入禁止地点が存在しないため、この中央値 \(T\) は目的地として常に有効です。 したがって、単に \(A\) の中央値 \(T\) を選び、そのときのコストの総和を計算するだけで最適解が得られます。

アルゴリズム

1. 友人たちの座標配列 \(A\) と立入禁止地点の配列 \(B\) をそれぞれ昇順にソートします。
2. \(A\) の最小値 \(A_{\min} = A[0]\) と最大値 \(A_{\max} = A[N-1]\) を取得します。
3. 二分探索（C++の std::upper_bound）を用いて、開区間 \((A_{\min}, A_{\max})\) に含まれる \(B\) の要素が存在するか判定します。
   • 具体的には、\(A_{\min}\) より大きい最小の \(B\) の要素が \(A_{\max}\) 未満であるかをチェックします。
   • 存在する場合は、全員が集まることは不可能なので -1 を出力して終了します。
4. 存在しない場合は、目的地 \(T\) を \(A\) の中央値 \(T = A[N/2]\) とします。
5. 各友人から \(T\) への距離の総和 \(\displaystyle\sum_{i=1}^{N} |A_i - T|\) を計算し、出力します。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 配列 \(A\) のソートに \(O(N \log N)\)、配列 \(B\) のソートに \(O(M \log M)\) かかります。
  • 二分探索（upper_bound）は \(O(\log M)\) です。
  • コストの総和の計算は \(O(N)\) です。
  • 全体としてソートがボトルネックとなり、実行時間制限に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 入力された配列 \(A\) と \(B\) を保持するためのメモリが必要です。

実装のポイント

• オーバーフローへの注意 座標の絶対値が最大で \(10^9\) であり、人数 \(N\) も最大で \(2 \times 10^5\) であるため、移動コストの総和は最大で約 \(2 \times 10^{14}\) に達します。32ビット整数型（int）ではオーバーフローするため、コストの計算や総和の保持には64ビット整数型（C++では long long）を使用する必要があります。

• 開区間の判定 「\(A_{\min}\) より大きく \(A_{\max}\) 未満」という開区間の条件を満たす \(B\) の要素があるかどうかは、std::upper_bound を用いることで \(O(\log M)\) でスマートに判定できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }

    // Sort both arrays to enable binary search and median finding
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    long long min_A = A.front();
    long long max_A = A.back();

    // Check if there is any forbidden point B_j strictly between min_A and max_A
    auto it = upper_bound(B.begin(), B.end(), min_A);
    if (it != B.end() && *it < max_A) {
        cout << -1 << "\n";
        return 0;
    }

    // The optimal meeting point T is the median of A
    long long T = A[N / 2];
    long long total_cost = 0;
    for (int i = 0; i < N; ++i) {
        total_cost += abs(A[i] - T);
    }

    cout << total_cost << "\n";

    return 0;
}

---

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