概要

都市を点として一直線上に置き、どの都市を \(1\) つ取り除いても残りが連結な通信網を作ります。
最小コストは、最も西の都市と最も東の都市の距離を \(2\) 倍した値、すなわち \(2(\max X_i - \min X_i)\) です。

考察

都市の位置を西から順に

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

と並べます。

結論から言うと、最適な通信網は次のように考えられます。

• 隣り合う都市同士をつなぐ
• さらに、最も西の都市 \(Y_1\) と最も東の都市 \(Y_N\) をつなぐ

つまり、都市を一直線上の順番でぐるっと一周する「サイクル」にします。

このときコストは

\[(Y_2 - Y_1) + (Y_3 - Y_2) + \cdots + (Y_N - Y_{N-1}) + (Y_N - Y_1)\]

です。

前半の隣接都市間の合計は

\[Y_N - Y_1\]

なので、合計は

\[2(Y_N - Y_1)\]

になります。

例えば都市の位置が \(0, 4, 10\) の場合、

• \(0\) と \(4\) をつなぐ：コスト \(4\)
• \(4\) と \(10\) をつなぐ：コスト \(6\)
• \(0\) と \(10\) をつなぐ：コスト \(10\)

合計は \(20 = 2(10 - 0)\) です。

この形はサイクルなので、どの都市を \(1\) つ取り除いても、残った都市たちは道のようにつながったままです。

---

では、なぜこれより安くできないのでしょうか。

隣り合う位置 \(Y_k\) と \(Y_{k+1}\) の間に「切れ目」を考えます。

この切れ目より西側の都市集合と、東側の都市集合に分けます。

もしこの切れ目をまたぐ通信回線が \(1\) 本しかないとします。
その唯一の回線の端点となっている都市を取り除くと、西側と東側をつなぐ回線がなくなり、ネットワークは分断されてしまいます。

したがって、条件を満たすためには、どの切れ目についても、その切れ目をまたぐ通信回線が少なくとも \(2\) 本必要です。

各通信回線のコストは、その回線がまたぐ切れ目の長さの合計です。
よって、すべての切れ目が少なくとも \(2\) 回ずつコストに数えられるため、総コストは少なくとも

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

です。

これは

\[2(Y_N - Y_1)\]

に等しいです。

つまり、

• \(2(Y_N - Y_1)\) 以上は必ず必要
• 実際に \(2(Y_N - Y_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)\)

実装のポイント

答えは最小値と最大値だけで決まります。

与えられる \(N\) は最大で \(10^6\) と大きいため、入力処理を高速に行うと安全です。
提示コードでは、入力全体をバイト列として読み取り、整数を手動でパースしています。

また、最初に出てくる整数は \(N\) なので、これは最小値・最大値の計算対象から除外しています。

ソースコード

import sys

data = sys.stdin.buffer.read()
mn = 10**18
mx = -1
num = 0
in_num = False
idx = 0

for c in data:
    if 48 <= c <= 57:
        num = num * 10 + (c - 48)
        in_num = True
    else:
        if in_num:
            if idx > 0:
                if num < mn:
                    mn = num
                if num > mx:
                    mx = num
            idx += 1
            num = 0
            in_num = False

if in_num and idx > 0:
    if num < mn:
        mn = num
    if num > mx:
        mx = num

print((mx - mn) * 2)

---

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