D - Practical Skill Test

問題

D - Practical Skill Test

感想

D解けた（小並感）

考え

Dの剰余で整理することが大事です。Dの剰余について、各移動をしていき、ans[D]に移動した時に使った値を追加していく。

Accepted Program

#include <iostream>
#include <string.h>
#include <set>
#include <vector>
#include <map>
#include <math.h>

using namespace std;
// #define ll long long
typedef long long ll;

int main () {
  ll  H, W, D;
  cin >> H >> W >> D;
  ll A[H][W];
  map <ll, ll> x;
  map <ll, ll> y;
  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      cin >> A[i][j];
      x[A[i][j]] = i;
      y[A[i][j]] = j;  
    }  
  }  
  ll Q;
  cin >> Q;
  ll L[Q], R[Q];
  
  // ここでDの剰余を計算しておく
  set<ll> mod;
  for (ll i = 0; i < Q; i++) {
    cin >> L[i] >> R[i];
    mod.insert(L[i] % D);  
  }
  vector<vector<ll> > ans;
  ans.resize(D);
  for (auto d : mod) {
    // dについて記入していく
    ll start = (ll) d;
    // ans[start]
    ans[start].push_back(0);
    ll end = start;
    while (end <= H * W) {
      ll before = end;
      end = end + D;
      if (end > H * W) {
        break;  
      }
      ll before_i = x[before];
      ll before_j = y[before];
      ll end_i = x[end];
      ll end_j = y[end];
      ll sub = ans[start][ans[start].size() - 1];
      ans[start].push_back(sub + abs(end_i - before_i) + abs(end_j - before_j));
    } 
  }
  for (ll i = 0; i < Q; i++) {
    ll sub = L[i] % D;
    R[i] = (R[i] - sub)/D;
    L[i] = (L[i] -sub )/D;
    cout << ans[sub][R[i]] - 
            ans[sub][L[i]] << endl;    
  }
  
}