概要

\(N\) 本の棒を「短くする操作のみ」で同じ長さに揃えるとき、必要な最小操作回数を求める問題です。

考察

重要な気づき

この問題のポイントは「棒は短くすることしかできない」という制約です。

棒を伸ばすことができないため、目標の長さ \(T\) は最も短い棒の長さ以下でなければなりません。

目標の長さはどう決めるべきか？

具体例で考えてみましょう。棒の長さが \([5, 3, 7]\) の場合：

• 目標を \(3\) にすると：\((5-3) + (3-3) + (7-3) = 2 + 0 + 4 = 6\) 回
• 目標を \(2\) にすると：\((5-2) + (3-2) + (7-2) = 3 + 1 + 5 = 9\) 回
• 目標を \(1\) にすると：\((5-1) + (3-1) + (7-1) = 4 + 2 + 6 = 12\) 回

目標を最小値の \(3\) より小さくすると、すべての棒に対して追加の操作が必要になり、操作回数が増えてしまいます。

結論

目標の長さを最小の棒の長さ \(\min(A)\) にするのが最適です。

これより大きくすると最小の棒を揃えられず、これより小さくすると無駄な操作が増えます。

アルゴリズム

1. 配列 \(A\) の最小値 \(M = \min(A)\) を求める
2. 各棒について、\((A_i - M)\) を計算し、その総和を求める
3. 総和が答え

数式で表すと： $\(\text{答え} = \sum_{i=1}^{N} (A_i - M) = \sum_{i=1}^{N} A_i - N \times M\)$

計算量

• 時間計算量: \(O(N)\)
  • 最小値の計算に \(O(N)\)
  • 総和の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) の格納に \(O(N)\)

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、操作回数の総和は最大で約 \(2 \times 10^{14}\) 程度になりえます
• Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long 型を使う必要があります
• sum() と min() を使えば、シンプルに実装できます

# 核心部分
min_length = min(a)  # 目標の長さ
total_operations = sum(x - min_length for x in a)  # 総操作回数

ソースコード

n = int(input())
a = list(map(int, input().split()))

# すべての棒を最小の長さに揃えるのが最適
# なぜなら、棒は短くすることしかできないので、
# 最小の棒より長くすることはできない
# また、最小の棒より短くすると余計な操作が必要

min_length = min(a)
total_operations = sum(x - min_length for x in a)
print(total_operations)

---

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