ABC089 Practical Skill Test

Submission #2702414 - AtCoder Beginner Contest 089

所見

クエリがたくさん来る問題が来たら脳死事前計算。制約を読み違えて無限にREした。眠かった(言い訳)

問題概要

H行W列のグリッドに1-H*Wまでの数字が重複なく書かれている。数Dが与えられるとき以下のクエリにQ<=10⁵回答えよ。
クエリ: 数L,Rが与えられる。
駒が数字Lが書かれているところに置いてある。一回の移動で駒をDだけ数字が大きい場所に移動させることができ、そのコストは移動前の座標と移動先の座標のマンハッタン距離で定義される。
この時、 数字Lが書かれているところからRが書かれているところまで移動させるときのコストを求めよ。ただし、R-LがDの倍数であることは保証される。

取った方針

クエリが10⁵個来るので、O(1)もしくはO(logHW)くらいでクエリを処理しなければならない。
クエリがたくさん来る（かつ問題の内容がクエリごとに変化しない）問題は事前計算をすることを考える。
駒はDずつしか移動しないので、移動コストは番号をDで割ったあまりで場合分けをすることができる。
一定区間の和を高速に求めるには累積和を用いればよい。
つまり、Dで割ったあまりごとにコストの累積和を計算しておけばクエリに対しO(1)で答えることができる。

正しい方針

上記

得られた知見

・クエリ大量->事前計算しておく
・区間の和を高速に求めたい->累積和
・独立に考えられるもの(今回の場合、Dで割った余りが違うマスに1つのクエリで行くことはない)を独立に考えることで問題が簡略化する

解くのに必要な要素

・事前計算
・累積和

周辺調査によって得られた知見

・特になし