Practical Skill Test [AtCoder Beginner Contest 089 D]

https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

解法

https://beta.atcoder.jp/contests/abc089/submissions/2161276

1-indexedを0-indexedに直して解く。
「g(x, y) := xからyへの経路にかかるコスト」とおくと、クエリは以下のように言い換えることができる。
g(L, R) = g(R % D, R) - g(L % D, L)
そのため、ちょっと言い換えた関数を考える。
「f(x) = g(x % D, x)」
これを計算するのにメモ化再帰を使おう。
f(x)はx ＜ Dであれば、これ以上小さくできないので、f(x)=0
D≦xであれば、-Dすることができるので、「f(x) = cost(x, x - D) + f(D)」
cost(x, x - D)はxとx-Dの座標を事前にidx配列で保存しておくと素早く計算することができる。
計算量はO(HW+Q)となり間に合う。

int H, W, D, A[303][303], Q;
pair<int, int> idx[90101];
//---------------------------------------------------------------------------------------------------
int memo[90101];
int f(int x) {
    if (0 < memo[x]) return memo[x];
    if (x < D) return 0;
 
    int y = x - D;
    int cost = abs(idx[x].first - idx[y].first) + abs(idx[x].second - idx[y].second);
    int res = cost + f(y);
    return memo[x] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> D;
    rep(y, 0, H) rep(x, 0, W) {
        cin >> A[y][x];
        A[y][x]--;
        idx[A[y][x]] = make_pair(x, y);
    }
    cin >> Q;
    rep(q, 0, Q) {
        int L, R; cin >> L >> R;
        L--; R--;
        int ans = f(R) - f(L);
        printf("%d\n", ans);
    }
}