概要

すべての花壇の水の量を等しくするために、各花壇に水を追加する最小コストを求める問題です。水は追加のみ可能なので、最大値に合わせるのが最適です。

考察

重要な気づき

この問題では「水を追加する」操作しかできません。水を減らすことはできないため、すべての花壇を揃える目標値は、現在の最大値以上でなければなりません。

なぜ最大値に揃えるのが最適か

目標値を \(T\) とすると、必要なコストは各花壇について \((T - A_i)\) の合計、つまり \(N \times T - \sum A_i\) となります。

• \(T\) が大きくなるほど、コストは増加します
• \(T\) は最小でも \(\max(A_i)\) 以上である必要があります（水を減らせないため）

したがって、\(T = \max(A_i)\) のときにコストが最小になります。

具体例

例えば、\(N = 3\)、\(A = [2, 5, 3]\) の場合を考えます。

• 最大値は \(5\)
• 花壇1: \(5 - 2 = 3\) リットル追加（3円）
• 花壇2: \(5 - 5 = 0\) リットル追加（0円）
• 花壇3: \(5 - 3 = 2\) リットル追加（2円）
• 合計: \(3 + 0 + 2 = 5\) 円

これは \(5 \times 3 - (2 + 5 + 3) = 15 - 10 = 5\) と計算できます。

アルゴリズム

1. 配列 \(A\) の最大値 \(\max(A)\) を求める
2. 配列 \(A\) の総和 \(\sum A_i\) を求める
3. 答えは \(\max(A) \times N - \sum A_i\)

この式の意味： - \(\max(A) \times N\)：すべての花壇を最大値に揃えたときの水の総量 - \(\sum A_i\)：現在の水の総量 - 差分が追加すべき水の量（＝コスト）

計算量

• 時間計算量: \(O(N)\)
  • 最大値の計算: \(O(N)\)
  • 総和の計算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するため

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、答えは最大で約 \(2 \times 10^{14}\) 程度になり得ます。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long 型を使う必要があります。

• Pythonの max() と sum() を使えば、簡潔に実装できます。

  ソースコード

N = int(input())
A = list(map(int, input().split()))

max_water = max(A)
total_cost = max_water * N - sum(A)

print(total_cost)

---

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