A 問題「ブロックの移動(Blocks)」解説

満点解法

$A$ の要素の総和は ${N*(N+1)}/2=1+2+...+N$ である．

したがって，

• ブロックが不足している山に，ブロックが不足していない山から余分なブロックを持ってくる

というシミュレーションを貪欲に繰り返すことで必ず最適に並び替えることができる．

ただし，シミュレーションを実装するよりも簡潔に答えを求める方法が存在する．

考えてみると，

• その山に持ってこなければならない(orその山から取り除かなければならない)ブロックの数は $|A_i-i|$ である．
• 各ブロックの不足ブロックの総和と余分なブロックの総和は一致している．
• これらを打ち消すように無駄なくブロックを動かせば最適である．

が分かる．

よって，最適な移動回数は ${{1}\over{2}}\sum_{i=1}^{N} {|A_i-i|}$ に等しい．