概要

駐車可能エリア \([0, M]\) の外にある車を、エリア内に移動させるための最小コストを求める問題です。各車を独立に考え、エリア外にある車だけを最寄りの境界まで移動させればよいです。

考察

重要な気づき

この問題のポイントは、各車は独立に移動できるという点です。つまり、ある車の移動が他の車の移動に影響を与えません。

各車について、以下の3つのケースに分けて考えます：

1. 座標が \(0\) 未満の場合: エリアの左側にはみ出しているので、座標 \(0\) まで移動させる必要がある
2. 座標が \(M\) より大きい場合: エリアの右側にはみ出しているので、座標 \(M\) まで移動させる必要がある
3. 座標が \(0\) 以上 \(M\) 以下の場合: すでにエリア内にいるので、移動不要

なぜ境界まで移動するのが最適か？

例えば、座標 \(-5\) にある車を考えます。この車をエリア内に入れるには、少なくとも座標 \(0\) まで移動させる必要があります。座標 \(0\) より先（例えば座標 \(3\)）まで移動させると、余計なコストがかかってしまいます。

したがって、エリア外の車は最寄りの境界（\(0\) または \(M\)）まで移動させるのが最適です。

具体例

\(N = 3\), \(M = 10\), \(A = [-3, 5, 15]\) の場合：

• 車1（座標 \(-3\)）: \(0\) まで移動 → コスト \(|-3 - 0| = 3\)
• 車2（座標 \(5\)）: すでにエリア内 → コスト \(0\)
• 車3（座標 \(15\)）: \(10\) まで移動 → コスト \(|15 - 10| = 5\)

合計コスト: \(3 + 0 + 5 = 8\)

アルゴリズム

1. 各車の座標 \(A_i\) について、以下を計算する：
   • \(A_i < 0\) ならば、コスト \(-A_i\)（= \(|A_i - 0|\)）を加算
   • \(A_i > M\) ならば、コスト \(A_i - M\)（= \(|A_i - M|\)）を加算
   • \(0 \leq A_i \leq M\) ならば、コスト \(0\)
2. すべての車のコストを合計して出力する

計算量

• 時間計算量: \(O(N)\)
  • 各車について1回ずつ判定・計算を行うだけ
• 空間計算量: \(O(N)\)
  • 入力を配列として保持する分（必要であれば \(O(1)\) にも削減可能）

実装のポイント

• 座標 \(A_i\) の範囲が \(-10^9\) から \(10^9\) まであるため、合計コストは最大で約 \(N \times 10^9 \approx 2 \times 10^{14}\) 程度になり得ます。64ビット整数型を使う必要がありますが、Pythonでは整数のオーバーフローを気にする必要はありません。

• 境界値の扱いに注意：\(A_i = 0\) や \(A_i = M\) の車は移動不要です（条件を \(<\) と \(>\) で正しく書く）。

  ソースコード

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    total_cost = 0
    for a in A:
        if a < 0:
            # 座標が0未満の場合、0まで移動
            total_cost += -a
        elif a > M:
            # 座標がMより大きい場合、Mまで移動
            total_cost += a - M
        # 0 <= a <= M の場合は移動不要（コスト0）
    
    print(total_cost)

solve()

---

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