2020-06-01 大手前プロコン 2019 B - 駒 (Pieces) https://atcoder.jp/contests/otemae2019/submissions/13761829 逆転の発想で「1箇所に集める」と考える 制約からまで処理して良いと分かる。問題文のとおりに「任意の駒を任意のマスに移動させる」とすると整理しづらいので、計算量から予想して逆転の発想で「1箇所に集める」と考えたい。集めるマス[i]に対して[i-K, i+K]の範囲から駒を集めることができるので、その範囲で駒が何個あるかカウントする。ただし、左と右の両方に駒があったとき、カウントできるのは片方だけなので注意する。
まで処理して良いと分かる。問題文のとおりに「任意の駒を任意のマスに移動させる」とすると整理しづらいので、計算量から予想して逆転の発想で「1箇所に集める」と考えたい。集めるマス[i]に対して[i-K, i+K]の範囲から駒を集めることができるので、その範囲で駒が何個あるかカウントする。ただし、左と右の両方に駒があったとき、カウントできるのは片方だけなので注意する。