概要

0度から出発し、N個の温度を全て訪問して0度に戻る際の最小移動コストを求める問題です。温度を数直線上の点と考えると、最適な経路を見つける問題に帰着できます。

考察

問題の言い換え

この問題は、数直線上で以下を行う最短経路問題と考えられます： - 始点：0 - 訪問すべき点：\(H_1, H_2, \ldots, H_N\) - 終点：0

重要な気づき

数直線上を移動するとき、同じ区間を何度も往復するのは無駄です。

具体例で考えてみましょう。\(H = \{-3, 2, 5\}\) の場合： - 訪問すべき点は -3, 2, 5 - 最小値は -3、最大値は 5

最適な戦略は、0度から一方の端（例えば5）まで行き、そこから反対の端（-3）まで行き、最後に0度に戻ることです。

0 → 5 → -3 → 0
コスト = 5 + 8 + 3 = 16

別の順番 \(0 → -3 → 5 → 0\) でも：

コスト = 3 + 8 + 5 = 16

どちらも同じ結果になります！

なぜこれが最適か

• 区間 \([\min, 0]\) と \([0, \max]\) をそれぞれ1往復ずつするのが最小
• 0度を起点・終点とするので、正の方向と負の方向をそれぞれ行って帰ってくる必要がある
• 途中の点は、この経路上で自然に訪問できる

最小コストの計算式

正の温度の最大値を \(\max\_positive\)、負の温度の最小値を \(\min\_negative\) とすると：

\[\text{最小コスト} = 2 \times \max\_positive + 2 \times (-\min\_negative)\]

これは \(2 \times (\max\_positive - \min\_negative)\) と同じです。

例：\(H = \{-3, 2, 5\}\) の場合 - \(\max\_positive = 5\) - \(\min\_negative = -3\) - コスト \(= 2 \times 5 + 2 \times 3 = 16\)

アルゴリズム

1. 全ての \(H_i\) を走査する
2. 正の温度の最大値 \(\max\_positive\)（初期値0）を更新
3. 負の温度の最小値 \(\min\_negative\)（初期値0）を更新
4. 答えは \(2 \times \max\_positive - 2 \times \min\_negative\)

ポイント: 初期値を0にすることで、全ての温度が正または負の場合も正しく処理できます。

• 全て正の場合：\(\min\_negative = 0\) となり、\(0 → \max → 0\) の往復
• 全て負の場合：\(\max\_positive = 0\) となり、\(0 → \min → 0\) の往復

計算量

• 時間計算量: \(O(N)\) - 配列を1回走査するだけ
• 空間計算量: \(O(N)\) - 入力配列の保持（最大・最小の計算だけなら \(O(1)\) でも可能）

実装のポイント

• \(H_i\) の値の範囲が \(-10^9 \leq H_i \leq 10^9\) と大きいので、答えは最大で約 \(4 \times 10^9\) になる。Python では整数オーバーフローの心配はないが、他の言語では long long 型を使う必要がある

• \(\max\_positive\) と \(\min\_negative\) の初期値を0にしておくことで、始点・終点の0度を自然に扱える

• ソートは不要で、最大値と最小値だけを求めればよい

  ソースコード

def solve():
    N = int(input())
    H = list(map(int, input().split()))
    
    # 最小エネルギー消費量を求める
    # 0度から始まり、全ての温度を訪問し、0度に戻る
    # 
    # 温度をソートして考える
    # 最適な経路は、0度から一方向に進み、戻ってきてもう一方向に進むパターン
    # または、0度から一方向だけ進んで戻るパターン
    
    # 全ての温度の最大値と最小値を求める
    # 0度も考慮する必要がある（開始点かつ終了点）
    
    if N == 0:
        print(0)
        return
    
    # 正の温度と負の温度に分ける
    max_positive = 0  # 正の温度の最大値（なければ0）
    min_negative = 0  # 負の温度の最小値（なければ0）
    
    for h in H:
        if h > max_positive:
            max_positive = h
        if h < min_negative:
            min_negative = h
    
    # 0度から開始して0度に戻る最小コスト
    # パターン1: 0 -> 正の最大 -> 負の最小 -> 0
    #   コスト = max_positive + (max_positive - min_negative) + (-min_negative) = 2*max_positive - 2*min_negative
    # パターン2: 0 -> 負の最小 -> 正の最大 -> 0
    #   コスト = (-min_negative) + (max_positive - min_negative) + max_positive = 2*max_positive - 2*min_negative
    # 
    # どちらも同じで、2 * (max_positive - min_negative)
    # ただし、max_positive >= 0, min_negative <= 0 なので
    # コスト = 2 * max_positive + 2 * (-min_negative) = 2 * max_positive - 2 * min_negative
    
    # 実際には、訪問する温度の範囲 [min_negative, max_positive] を1往復するのが最適
    # 0度が含まれているので、0度から出発して片方の端に行き、もう片方の端に行って0度に戻る
    # これで全ての温度を訪問できる
    
    result = 2 * max_positive - 2 * min_negative
    print(result)

solve()

---

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