7K12 blog

猫でも分かるアルゴリズム解説

大手前プロコン 2019 B - 駒 (Pieces)

f:id:tkr987:20200601003236p:plain

https://atcoder.jp/contests/otemae2019/submissions/13761829

  • 逆転の発想で「1箇所に集める」と考える

f:id:tkr987:20200601003410p:plain

制約から O(N^2)まで処理して良いと分かる。問題文のとおりに「任意の駒を任意のマスに移動させる」とすると整理しづらいので、計算量から予想して逆転の発想で「1箇所に集める」と考えたい。集めるマス[i]に対して[i-K, i+K]の範囲から駒を集めることができるので、その範囲で駒が何個あるかカウントする。ただし、左と右の両方に駒があったとき、カウントできるのは片方だけなので注意する。