概要

\(N\) 個のりんごの重さを、削る作業によってすべて等しくするとき、削る量の合計を最小化する問題です。各りんごには一律でコーティング剤の重さ \(R\) が加わっています。

考察

この問題を解くためのポイントは、「目標とする重さをいくらに設定すれば、削る量を最小にできるか」を考えることです。

1. 目標とする重さ \(X\) の決定

各りんごのコーティング後の重さは \(A_i + R\) グラムです。 りんごを「削る」ことはできますが「増やす」ことはできないため、すべてのりんごを同じ重さ \(X\) にするためには、\(X\) はすべてのりんごの現在の重さ以下である必要があります。 つまり、\(X \leq \min(A_1+R, A_2+R, \dots, A_N+R)\) です。

削る量を最小限にするには、最終的な重さ \(X\) をできるだけ大きくすればよいため、\(X\) を「コーティング後の重さの最小値」に設定するのが最適です。 $\(X = \min(A_i + R)\)$

2. コーティング剤 \(R\) の影響

各りんごから削る量は、\((\text{現在の重さ}) - (\text{目標の重さ } X)\) で計算できます。 りんご \(i\) について計算すると以下のようになります： $\((A_i + R) - (\min(A) + R) = A_i - \min(A)\)$

ここで重要な事実に気づきます。すべてのりんごに同じ量 \(R\) が足されているため、りんご同士の重さの差はコーティング前後で変わりません。 したがって、最小化を考える上で \(R\) の値は結果に影響を与えないことになります。

3. 具体例

例えば \(A = [10, 12, 15], R = 5\) の場合： - コーティング後：\([15, 17, 20]\) - 最小値は \(15\) なので、目標の重さを \(15\) にする。 - 削る量：\((15-15) + (17-15) + (20-15) = 0 + 2 + 5 = 7\)

これは、元の重さ \(A\) の最小値 \(10\) を基準に計算した結果 \((10-10) + (12-10) + (15-10) = 7\) と一致します。

アルゴリズム

1. 入力された \(A_1, A_2, \dots, A_N\) の中から最小値 \(min\_A\) を見つける。
2. 各 \(A_i\) について、\(A_i - min\_A\) を計算し、その総和を求める。
   • 数式で表すと：\(\sum_{i=1}^{N} (A_i - \min(A))\)
   • 計算を工夫すると：\((\sum A_i) - N \times \min(A)\) としても求められます。

計算量

• 時間計算量: \(O(N)\)
  • リストの最小値の探索に \(O(N)\)、合計の計算に \(O(N)\) かかります。\(N \leq 2 \times 10^5\) なので、十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の重さをリストに保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(R\) の値は非常に大きくなる可能性がありますが、考察の通り計算には不要なため、無視して実装して問題ありません。

• 合計値が \(2^{31}-1\) を超える可能性があるため、プログラミング言語によっては 64 ビット整数型（Python の場合は標準で対応）を使用するように注意しましょう。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの個数, R: コーティング剤の重さ
    N = int(input_data[0])
    R = int(input_data[1])
    
    # A: 各りんごの元の重さ
    A = list(map(int, input_data[2:]))
    
    # コーティング後の各りんごの重さは W_i = A_i + R
    # すべてのりんごの重さを等しくするために削る量を最小にするには、
    # 目標とする重さ X を「コーティング後の重さの最小値」に設定すればよい。
    # X = min(A_1 + R, A_2 + R, ..., A_N + R) = min(A) + R
    
    # 各りんごから削る量は (A_i + R) - X
    # (A_i + R) - (min(A) + R) = A_i - min(A)
    
    # したがって、削る量の合計は sum(A_i - min(A)) となる
    # これは R の値に依存しない
    
    min_a = min(A)
    total_shaved = sum(A) - N * min_a
    
    print(total_shaved)

if __name__ == '__main__':
    solve()

---

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