概要

この問題は、一直線上に並んだ \(N\) 個の都市を、「どの1つの都市が故障しても、残りの都市が互いに通信できる」という条件（2-頂点連結性）を満たしつつ、最小のコストで結ぶネットワークを構築する問題です。

考察

1. 条件の言い換え

「任意の1つの都市を取り除いても、残りの都市が連結である」という条件は、グラフ理論における 2-頂点連結 (2-vertex-connected) の定義そのものです。\(N \geq 3\) において、この条件を満たす最もシンプルな構造は「サイクル（閉路）」です。

2. カットによる下限の検討

都市を位置の昇順に並べて \(x_1 < x_2 < \dots < x_N\) とします。 任意の \(m\) (\(1 \leq m < N\)) について、集合 \(\{x_1, \dots, x_m\}\) と \(\{x_{m+1}, \dots, x_N\}\) を分ける境界（カット）を考えます。

もしこの境界をまたぐ通信回線が 1本 しかなければ、その回線の端点となっている都市が故障した際、ネットワークは分断されてしまいます。したがって、条件を満たすためには、どの隣接する都市間の隙間も 少なくとも 2本の回線 がまたいでいなければなりません。

3. 最小コストの導出

各区間 \((x_m, x_{m+1})\) を少なくとも 2本の回線が通る必要があるため、総コスト \(L\) は以下の下限を持ちます。 $\(L \geq \sum_{m=1}^{N-1} 2 \times (x_{m+1} - x_m) = 2 \times (x_N - x_1)\)$

この下限値 \(2 \times (\max(X_i) - \min(X_i))\) は、実際に達成可能です。例えば、都市を順番に結び、最後に両端を結ぶハミルトン閉路 \(x_1 \to x_2 \to \dots \to x_N \to x_1\) を作れば、コストは以下のようになります。 - 隣接する都市間のコストの和: \((x_2-x_1) + (x_3-x_2) + \dots + (x_N-x_{N-1}) = x_N - x_1\) - 両端 \(x_1\) と \(x_N\) を直接結ぶコスト: \(x_N - x_1\) - 合計: \(2(x_N - x_1)\)

このサイクル構造は \(N \geq 3\) において 2-頂点連結であるため、これが最小コストとなります。

アルゴリズム

与えられた都市の位置 \(X_i\) の中から、最大値と最小値を求めるだけで答えが得られます。

1. 都市の位置の最大値 \(\max(X)\) と最小値 \(\min(X)\) を求める。
2. \(2 \times (\max(X) - \min(X))\) を計算して出力する。

ソートを行う必要はなく、入力を 1 回走査するだけで計算可能です。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を 1 度ずつ確認して最大値と最小値を求めるため。
• 空間計算量: \(O(1)\)
  • 入力を逐次処理すれば、全ての値をメモリに保持する必要もありません。

実装のポイント

• オーバーフローへの注意: \(X_i\) が最大 \(10^9\) なので、答えは最大で \(2 \times 10^9\) 程度になります。C++ の int 型（32bit 符号付き整数）の最大値は約 \(2.14 \times 10^9\) なのでギリギリ収まりますが、安全のために long long 型（64bit 整数）を使用するのが無難です。

• 効率的な入出力: \(N\) が \(10^6\) と大きいため、C++ の場合は std::ios::sync_with_stdio(false); std::cin.tie(nullptr); を用いて入出力を高速化することが推奨されます。

  ソースコード

#include <iostream>
#include <algorithm>

/**
 * Problem: Disaster-Resistant Communication Network
 * 
 * The condition for the network is that removing any single city v and its incident edges
 * must leave the remaining N-1 cities connected. This is the definition of a 
 * 2-vertex-connected graph.
 * 
 * For N cities located at positions X_1, X_2, ..., X_N on a line, let the sorted 
 * positions be x_1 < x_2 < ... < x_N. 
 * Any 2-vertex-connected graph must also be 2-edge-connected. For any cut 
 * separating {x_1, ..., x_m} and {x_{m+1}, ..., x_N}, there must be at least 
 * two edges crossing it. 
 * 
 * If c_m is the number of edges crossing the cut between x_m and x_{m+1}, the 
 * total cost is sum_{m=1}^{N-1} c_m * (x_{m+1} - x_m).
 * For a 2-vertex-connected graph where N >= 3, it can be shown that c_m >= 2 
 * for all m = 1, ..., N-1.
 * 
 * The minimum possible cost is achieved when c_m = 2 for all m, which gives:
 * Cost = sum_{m=1}^{N-1} 2 * (x_{m+1} - x_m) = 2 * (x_N - x_1).
 * 
 * This cost is achievable by a Hamiltonian cycle, such as x_1 -> x_2 -> ... -> x_N -> x_1,
 * which is 2-vertex-connected.
 * 
 * Thus, the minimum cost is 2 * (max(X_i) - min(X_i)).
 */

int main() {
    // Optimize standard I/O for competitive programming
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    if (!(std::cin >> N)) return 0;

    // Use long long to prevent potential overflow, although 2 * 10^9 fits in int.
    // X_i are given up to 10^9, and N is up to 10^6.
    long long x;
    if (!(std::cin >> x)) return 0;
    
    long long min_x = x;
    long long max_x = x;

    // Iterate through the remaining N-1 cities to find the minimum and maximum positions.
    for (int i = 1; i < N; ++i) {
        if (!(std::cin >> x)) break;
        if (x < min_x) min_x = x;
        if (x > max_x) max_x = x;
    }

    // The minimum cost to satisfy the 2-vertex-connectivity condition.
    long long min_total_cost = 2 * (max_x - min_x);

    // Output the result as an integer.
    std::cout << min_total_cost << std::endl;

    return 0;
}

---

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