概要

都市が一直線上にあるとき、どの都市を \(1\) つ取り除いても残りが連結であるような通信ネットワークを、最小コストで作る問題です。

答えは非常にシンプルで、都市の最西端の位置を \(\min X_i\)、最東端の位置を \(\max X_i\) とすると、最小コストは

\(2(\max X_i - \min X_i)\)

になります。

考察

都市を西から東に並べたものを

\(Y_1 < Y_2 < \cdots < Y_N\)

とします。

このとき、隣り合う都市の間の区間、つまり

\(Y_i\) と \(Y_{i+1}\) の間

に注目します。

この区間をまたぐ通信回線が \(1\) 本以下しかないとします。

すると、その回線の端点になっている都市を取り除くことで、この区間の西側と東側をつなぐ回線がなくなってしまいます。
その結果、残った都市が互いに通信できなくなり、条件を満たせません。

したがって、すべての隣接区間について、その区間をまたぐ通信回線は少なくとも \(2\) 本必要です。

ここで、ある通信回線が \(Y_l\) と \(Y_r\) を結んでいるとします。
そのコストは

\(Y_r - Y_l\)

です。これは、途中にある隣接区間の長さの合計と考えられます。

つまり、通信回線の総コストは、

「各隣接区間の長さ」\(\times\)「その区間をまたぐ回線の本数」

の合計として考えることができます。

各隣接区間をまたぐ回線は少なくとも \(2\) 本必要なので、総コストは少なくとも

\(2 \times \{(Y_2 - Y_1) + (Y_3 - Y_2) + \cdots + (Y_N - Y_{N-1})\}\)

です。

これは望遠和により、

\(2(Y_N - Y_1)\)

になります。

つまり、どんなネットワークを作っても、コストは最低でも

\(2(\max X_i - \min X_i)\)

必要です。

一方で、この値は実際に達成できます。

都市を西から東の順に並べて、

\(Y_1 - Y_2 - Y_3 - \cdots - Y_N - Y_1\)

というサイクルを作ります。

このときのコストは、

• 隣り合う都市を結ぶコストの合計が \(Y_N - Y_1\)
• 最後に \(Y_N\) と \(Y_1\) を結ぶコストが \(Y_N - Y_1\)

なので、合計は

\(2(Y_N - Y_1)\)

です。

サイクルは、どの \(1\) 頂点を取り除いても残りが道になり、連結のままです。
よって条件を満たします。

したがって、最小コストは

\(2(\max X_i - \min X_i)\)

です。

素朴にすべての都市間の通信回線を考えると、候補の回線数は \(O(N^2)\) 本あります。
しかし、\(N \leq 10^6\) なので、全組み合わせを調べる方法は実行不可能です。

この問題では、最終的な答えが最西端と最東端の都市だけで決まることに気づくのが重要です。

アルゴリズム

入力された都市の位置 \(X_i\) について、最小値と最大値を求めます。

1. \(\min X_i\) を求める
2. \(\max X_i\) を求める
3. \(2(\max X_i - \min X_i)\) を出力する

都市を実際にソートする必要はありません。
最小値と最大値だけ分かれば十分です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

答えは

\(2(\max X_i - \min X_i)\)

です。

入力を読みながら、最小値 mn と最大値 mx を更新していけばよいです。

long long mn = LLONG_MAX, mx = LLONG_MIN;

for (int i = 0; i < N; i++) {
    long long x;
    cin >> x;
    mn = min(mn, x);
    mx = max(mx, x);
}

cout << 2 * (mx - mn) << '\n';

位置の値は最大 \(10^9\) ですが、安全のため long long を使うと安心です。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long mn = LLONG_MAX, mx = LLONG_MIN;
    for (int i = 0; i < N; i++) {
        long long x;
        cin >> x;
        mn = min(mn, x);
        mx = max(mx, x);
    }

    cout << 2 * (mx - mn) << '\n';
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。