概要

全てのりんご（コーティング後）の重さを同じにするために削る量の合計を最小化する問題です。結論として、答えは \(R\) に依らず \( \sum A_i - N \cdot \min(A_i)\) になります。

考察

重要な気づき

コーティング後の重さは各りんごで一様に \(+R\) され、\(B_i = A_i + R\) になります。
ここから各りんごを削って全て \(X\) に揃えるとき、必要な削る量は各りんごで \((B_i - X)\)（ただし \(X \le B_i\) が必要）なので、合計は

\([ \sum_{i=1}^{N} (B_i - X) = \sum B_i - N X ]\)

となります。これは \(X\) が大きいほど合計が小さくなる（\(-NX\) なので）ため、可能な範囲で最大の \(X\) を選べばよいです。

削ることしかできないので、全てのりんごで \(X \le B_i\) が必要です。したがって取り得る最大の \(X\) は

\([ X = \min_i B_i ]\)

です。

\(R\) が効かない理由

\(\min_i B_i = \min_i (A_i + R) = \min_i A_i + R\) であり、

\([ \sum B_i - N\min B_i = \left(\sum (A_i + R)\right) - N(\min A_i + R) = \left(\sum A_i + NR\right) - (N\min A_i + NR) = \sum A_i - N\min A_i ]\)

となって \(R\) が完全に打ち消し合うため、入力の \(R\) は答えに影響しません。

素朴なアプローチが危険な理由

例えば \(X\) をいろいろ試して最小値を探す（全探索や二分探索）方針だと、\(X\) の範囲は最大で \(10^9\) 以上あり、\(N\) も \(2\times10^5\) と大きいので現実的ではありません。
上の観察により、「最適な \(X\) は最小値に一致する」と分かれば、探索なしで一発で答えが出せます。

具体例

\(A=[3,7,5], R=2\) とすると、コーティング後は \(B=[5,9,7]\)。
揃えられる最大の \(X\) は \(\min(B)=5\)。削る量は \((5-5)+(9-5)+(7-5)=0+4+2=6\)。
式でも \(\sum A - N\min A = (3+7+5) - 3\cdot 3 = 15-9=6\) で一致します。

アルゴリズム

1. 入力 \(A_1,\dots,A_N\) を読む（\(R\) は読めばよいが計算には不要）。
2. \(m = \min(A)\) を求める。
3. \(s = \sum A\) を求める。
4. 答え \(s - N\cdot m\) を出力する。

これは「最小のりんごに合わせるのが最適」であり、他のりんごはそこまで削る、という意味になります。

計算量

• 時間計算量: \(O(N)\)（最小値と総和を1回ずつ計算）
• 空間計算量: \(O(N)\)（コードでは配列に保持しているため。逐次処理なら \(O(1)\) も可能）

実装のポイント

• 合計や \(N\cdot \min(A)\) は最大で \(2\times10^5 \times 10^9 = 2\times10^{14}\) 程度になり得ます。Python の int は多倍長なのでそのままで安全です（他言語なら 64bit 整数を使用）。

• 入力が大きいので、sys.stdin.buffer.read() を使った高速入力にしてあります。

• 問題文上はコーティング後の重さで考えますが、結論的に \(R\) は相殺されるため計算に入れる必要はありません。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    R = next(it)  # not needed for the result
    A = [next(it) for _ in range(N)]
    m = min(A)
    s = sum(A)
    print(s - N * m)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。