概要

\(N\) 台の車を、それぞれの現在位置から指定された範囲 \([0, M]\) 内に移動させるための最小コスト（移動距離の合計）を求める問題です。

考察

この問題の核心は、「各車は他の車とは独立に移動させることができる」という点にあります。したがって、全体の合計コストを最小化するためには、それぞれの車について「その車を範囲 \([0, M]\) 内に入れるための最小コスト」を個別に計算し、それらを合計すればよいことになります。

ある車が座標 \(x\) にあるとき、その車を範囲 \([0, M]\) 内に移動させるための最小コストは、以下のように分類できます。

1. \(x < 0\) の場合 範囲内で最も \(x\) に近い座標は \(0\) です。したがって、座標 \(0\) まで移動させるのが最適であり、コストは \(0 - x = -x\) となります。
2. \(0 \leq x \leq M\) の場合 既に車は駐車可能エリア内にあります。移動させる必要はないため、コストは \(0\) です。
3. \(x > M\) の場合 範囲内で最も \(x\) に近い座標は \(M\) です。したがって、座標 \(M\) まで移動させるのが最適であり、コストは \(x - M\) となります。

このように、各車に対して単純な条件分岐を行うだけで、最適な移動距離を求めることができます。

アルゴリズム

1. 合計コストを保持する変数 total_cost を \(0\) で初期化します。
2. 各車の座標 \(A_i\) を順番に確認します。
   • \(A_i < 0\) であれば、 total_cost に \(-A_i\) を加算します。
   • \(A_i > M\) であれば、 total_cost に \(A_i - M\) を加算します。
   • それ以外（\(0 \leq A_i \leq M\)）の場合は、何もしません。
3. すべての車について計算が終わった後、 total_cost を出力します。

計算量

• 時間計算量: \(O(N)\) 車の台数 \(N\) に対して、各要素を \(1\) 回ずつ走査して定数時間の判定を行うため、線形時間で処理が完了します。
• 空間計算量: \(O(N)\) 入力をすべてリスト等に格納する場合、 \(N\) 台分の座標を保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 大きな数値の扱い: 合計コストは非常に大きな値（最大で \(2 \times 10^{14}\) 程度）になる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせずに計算できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # N: 車の台数, M: 駐車可能エリアの上限座標
    n = int(input_data[0])
    m = int(input_data[1])
    
    # a: 各車の現在の座標
    a = map(int, input_data[2:])
    
    total_cost = 0
    for x in a:
        # 座標が 0 未満の場合、0 まで移動させるコストを加算
        if x < 0:
            total_cost += -x
        # 座標が M より大きい場合、M まで移動させるコストを加算
        elif x > m:
            total_cost += x - m
            
    # 合計コストを出力
    print(total_cost)

if __name__ == '__main__':
    solve()

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