概要

一本道上の \(N\) 都市に対して、任意の1都市を除去してもネットワークが連結であり続ける（2頂点連結な）通信ネットワークを最小コストで構築する問題です。答えは \(2 \times (\max(X_i) - \min(X_i))\) です。

考察

災害耐性条件の言い換え

「任意の1都市とそれに接続する回線を取り除いても残りが連結」という条件は、グラフ理論における2頂点連結（biconnected）の定義そのものです。

下界の導出

2頂点連結グラフでは、任意の2頂点間に辺素な（edge-disjoint）2本のパスが存在します（Whitneyの定理）。

最も左の都市 \(x_{\min}\) と最も右の都市 \(x_{\max}\) の間に辺素な2本のパスが必要です。一本道上では、2点間のパスのコストは（どの中継点を通っても）少なくとも2点間の距離 \(x_{\max} - x_{\min}\) になります（三角不等式より）。

したがって、コストの下界は \(2 \times (x_{\max} - x_{\min})\) です。

上界の構成（最適解の実現）

都市を座標順にソートして \(x_1 < x_2 < \cdots < x_n\) とし、ハミルトン閉路（すべての都市を座標順に一周する巡回路）を考えます：

\[x_1 \to x_2 \to x_3 \to \cdots \to x_n \to x_1\]

このコストは： - 前方のパス：\((x_2 - x_1) + (x_3 - x_2) + \cdots + (x_n - x_{n-1}) = x_n - x_1\)（テレスコーピング） - 閉じる辺：\(x_n - x_1\)

合計 \(2(x_n - x_1) = 2(x_{\max} - x_{\min})\) で、下界に一致します。

また、\(n \geq 3\) 頂点の閉路は2頂点連結です（任意の1頂点を除いてもパスが残り連結）。

結論

下界と上界が一致するため、最小コストは \(2 \times (\max(X_i) - \min(X_i))\) です。

アルゴリズム

1. 全都市の座標を読み込み、最小値 \(\min\) と最大値 \(\max\) を求める。
2. \(2 \times (\max - \min)\) を出力する。

ソートすら不要で、最小値と最大値だけが必要です。

計算量

• 時間計算量: \(O(N)\)（全座標を1回走査するだけ）
• 空間計算量: \(O(1)\)（座標を保持する必要なし）

実装のポイント

• \(X_i\) は最大 \(10^9\) で、答えは最大 \(2 \times 10^9\) になるため、long long を使用する。

• 都市の座標をすべて保持する必要がなく、読みながら最小値・最大値を更新すればよい。これにより \(N = 10^6\) でも高速かつ省メモリで動作する。

  ソースコード

#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 << 2LL * (mx - mn) << "\n";
    return 0;
}

---

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