概要

数直線上の \(0\) の地点から出発し、与えられた \(N\) 個の地点（温度 \(H_i\)）をすべて訪れてから再び \(0\) に戻るまでの、最短移動距離を求める問題です。

考察

この問題は、「数直線上の複数の点をすべて回って元の場所に戻る」という設定に置き換えて考えることができます。

重要な気づき

数直線上の点（温度）を効率よく回るためには、あちこちを行ったり来たりするのではなく、端から端まで一気に移動するのが最も効率的です。

1. 訪れるべきすべての地点（試薬の温度 \(H_1, \dots, H_N\)）と、開始・終了地点である \(0\) を合わせた集合を考えます。
2. この集合の中の最小値を \(min\_temp\)、最大値を \(max\_temp\) とします。
3. どのような順番で回ったとしても、すべての地点を訪れて \(0\) に戻るためには、少なくとも \(min\_temp\) から \(max\_temp\) までの区間を「往復」する必要があります。

なぜ「(最大値 - 最小値) × 2」になるのか？

例えば、温度が \(\{-5, 10\}\) で開始地点が \(0\) の場合を考えます。 - 訪れるべき点は \(\{-5, 0, 10\}\) です。 - 最小値は \(-5\)、最大値は \(10\) です。 - 最短経路の例： \(0 \to -5 \to 10 \to 0\) - 移動距離： \(|-5 - 0| + |10 - (-5)| + |0 - 10| = 5 + 15 + 10 = 30\) - これは、\((10 - (-5)) \times 2 = 15 \times 2 = 30\) と一致します。

数直線上の最も左にある点から最も右にある点まで移動し、そこから戻ってくることで、その間にあるすべての点は必ず通過することになります。したがって、最適な戦略は「左端まで行って右端まで行く（またはその逆）」となり、その合計距離は「（最大値 - 最小値）の2倍」となります。

アルゴリズム

1. 与えられた \(N\) 個の温度 \(H_i\) に、開始地点である \(0\) を加えたリストを作成します。
2. そのリストの中から最大値 \(max\_temp\) と最小値 \(min\_temp\) を見つけます。
   • 提供されたコードでは、ソート（sorted）を行うことで、最初の要素を最小値、最後の要素を最大値として取得しています。
3. \((max\_temp - min\_temp) \times 2\) を計算して出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の要素のソートに \(O(N \log N)\) かかります。
  • ※単に最大値と最小値を求めるだけであれば \(O(N)\) で解くことも可能です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の温度を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 開始地点 \(0\) の扱い: 試薬の温度がすべて正の場合や、すべて負の場合があります。その場合でも必ず \(0\) に戻る必要があるため、最大値・最小値を判定する対象に \(0\) を含めることが必須です。

• 重複の削除: 提供されたコードでは set を使用して重複を削除しています。計算量に大きな影響はありませんが、メモリの節約や処理の整理に役立ちます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、トークンに分割します
    # この手法は大量の入力を効率的に処理するのに適しています
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 試薬の温度設定（H_i）を整数に変換し、セット（集合）に格納します
    # また、開始点および終了点である「0度」を必ず含めるようにします
    # セットを使用することで重複する温度を1つにまとめ、処理を効率化します
    temp_points = set(map(int, input_data[1:]))
    temp_points.add(0)
    
    # 温度の集合を昇順にソートします
    # 0度を含めた全温度を訪問して0度に戻るための最小コストは、
    # 数直線上の「最も低い温度」から「最も高い温度」までの距離の2倍になります
    sorted_points = sorted(temp_points)
    
    # ソートされたリストの最初（最小値）と最後（最大値）の要素から全範囲を求めます
    # 0がリストに含まれているため、この範囲は必ず開始点と終了点をカバーします
    min_temp = sorted_points[0]
    max_temp = sorted_points[-1]
    
    # 全移動距離（エネルギー消費量の合計）は (最大温度 - 最小温度) * 2 です
    # 既存のループによる最大・最小値探索とは異なり、ソートを利用したアプローチです
    print((max_temp - min_temp) * 2)

if __name__ == "__main__":
    main()

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