概要

\(N\) 個のりんごにコーティング剤を塗った後、すべてのりんごを同じ重さにするために削る量の合計を最小化する問題です。

考察

重要な気づき

1. りんごは削ることしかできない（重さを減らすことしかできない）

   • これは、目標の重さ \(X\) を最も軽いりんごより重くすることはできないことを意味します
   • もし \(X\) が最軽量のりんごより重ければ、そのりんごの重さを \(X\) にすることが不可能です

2. 削る量の合計を数式で表す

   • コーティング後の各りんごの重さを \(W_i = A_i + R\) とします
   • すべてのりんごを重さ \(X\) にするとき、削る量の合計は： $\(\sum_{i=1}^{N} (W_i - X) = \sum_{i=1}^{N} W_i - N \times X\)$

3. 削る量を最小化するには？

   • 上の式を見ると、\(\sum W_i\) は固定値なので、\(N \times X\) を最大化すれば良いことがわかります
   • つまり、\(X\) を最大化すれば削る量は最小になります

4. \(X\) の最大値は？

   • \(X\) は最も軽いりんごの重さ \(\min(W_i)\) 以下でなければなりません
   • したがって、\(X = \min(W_i)\) が最適です

具体例で確認

例えば、コーティング後の重さが \([5, 8, 6]\) の場合： - 最小値は \(5\) なので、目標の重さ \(X = 5\) - 削る量 = \((5-5) + (8-5) + (6-5) = 0 + 3 + 1 = 4\)

これは \(\sum W_i - N \times X = (5+8+6) - 3 \times 5 = 19 - 15 = 4\) と一致します。

アルゴリズム

1. 各りんごのコーティング後の重さ \(W_i = A_i + R\) を計算する
2. コーティング後の重さの最小値 \(\min(W_i)\) を求める
3. コーティング後の重さの総和 \(\sum W_i\) を求める
4. 削る量の合計 \(= \sum W_i - N \times \min(W_i)\) を出力する

計算量

• 時間計算量: \(O(N)\)
  • 配列の総和を求めるのに \(O(N)\)
  • 最小値を求めるのに \(O(N)\)
• 空間計算量: \(O(N)\)
  • コーティング後の重さを格納する配列に \(O(N)\)
  • （最適化すれば \(O(1)\) にもできますが、可読性のため配列を使用）

実装のポイント

• \(R\) や \(A_i\) の値が最大 \(10^9\) まであり、\(N\) が最大 \(2 \times 10^5\) なので、総和は最大で約 \(2 \times 10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、他の言語（C++ など）では 64 ビット整数型を使う必要があります。

• コーティング後の重さを別配列に保存せず、直接 min(A) + R と sum(A) + N * R を計算することもできます。

  ソースコード

def solve():
    N, R = map(int, input().split())
    A = list(map(int, input().split()))
    
    # コーティング後の重さ
    weights = [a + R for a in A]
    
    # すべてのりんごの重さを等しくするために削る量の合計を最小にする
    # 最終的な重さ X は、最小の重さ以下でなければならない（増やすことはできないため）
    # 削る量の合計 = Σ(weights[i] - X) = Σweights[i] - N * X
    # これを最小化するには X を最大化すればよい
    # X の最大値は min(weights) である
    
    min_weight = min(weights)
    total_sum = sum(weights)
    
    # 削る量の合計 = 総重量 - N * (目標重さ)
    result = total_sum - N * min_weight
    
    print(result)

solve()

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