概要

すべてのりんごの重さをコーティング後に同じにするために削る量の合計を最小化する問題です。

考察

各りんごには \(R\) グラムのコーティングが施され、りんご \(i\) の重さは \(A_i + R\) になります。
高橋君の目標は、すべてのりんごの重さを同じ値 \(X\) にすることです。
ただし、重さを増やすことはできないので、削ることしかできません。

ここで重要な観察があります：
削る量を最小にするには、すべてのりんごの重さを「最も軽いりんごの重さ」に揃えるのが最適です。

なぜなら、もし目標の重さ \(X\) が「最も軽いりんごの重さ」より軽ければ、そのりんごは目標に到達できません（削るだけなので）。
また、もし \(X\) が「最も軽いりんごの重さ」より重ければ、全体的に削る量が多くなり非効率です。

したがって、コーティング後の重さのリスト \([A_1 + R, A_2 + R, ..., A_N + R]\) の中で最小のものを求め、他のりんごはそれまで削るのが最適です。

例えば、\(A = [3, 1, 4], R = 2\) の場合： - コーティング後：\([5, 3, 6]\) - 最小値は 3 - 削る量は \((5-3) + (3-3) + (6-3) = 2 + 0 + 3 = 5\)

このようにすれば、削る量の合計が最小になります。

アルゴリズム

1. 各りんごのコーティング後の重さを計算する：\(A_i + R\)
2. その中の最小値を求める
3. 各りんごの重さから最小値を引いたものを合計する

この合計が答えです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

（重さリストを作成しているため。必要に応じて空間計算量を \(O(1)\) にすることも可能）

実装のポイント

• 入力を高速に読み込む（sys.stdin.read を使用）
• 各りんごの重さに \(R\) を足してリストを作る
• 最小値を求め、それとの差分を合計する

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    R = int(data[1])
    A = list(map(int, data[2:]))

    # コーティング後の重さ
    coated_weights = [a + R for a in A]

    # 最小の重さに合わせるのが最適
    min_weight = min(coated_weights)

    # 削る量の合計
    total_cut = sum(w - min_weight for w in coated_weights)

    print(total_cut)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。