緑コーダーの参加記録: ABC186 B - Blocks on Grid

問題

https://atcoder.jp/contests/abc186/tasks/abc186_b

解法

開く

すべてのマスの値の合計 $S$ と最小値 $M$ を計算し、 $S - HWM$ を出力する。

解説

どのマスにも同じ個数のブロックがあるようにするには、適切な個数のブロックを取り除く必要があります。
少なくとも１つは最もブロックが少ないマスがあり、そのようなマスからはブロックを取り除いても無駄になります。
そこで、最小でないマスから、最小になるようにブロックを取り除くことを考えます。
最小を $M$ とすると、それぞれのマス $A_{i,j}$ において $A_{i, j} - M$ 個取り除けば良いことがわかります。
この総和を取ると $\sum_{i = 1}^{H} \sum_{j = 1}^{W} (A_{i, j} - M) = \sum_{i = 1}^{H} \sum_{j = 1}^{W} A_{i, j} - HWM$ となります。

ポイント

• 最小値に揃えるには、最小値との差

コード

abc186_b.rb

H, W = gets.split.map(&:to_i)
A = Array.new(H) { gets.split.map(&:to_i) }
S = A.sum(&:sum)
M = A.map(&:min).min
puts S - H * W * M