📘

ABC 089 | D - Practical Skill Test

2020/12/29に公開

競プロ

累積和

飛び飛びの累積和

tech

問題

解法

貪欲にやったらTLEしてしまう。 $L_i$ から $R_i$ までを $O(1)$ で求められるように考える必要がある。
マスの値は $1$ から $H \times N$ まであり、 $D$ が固定なので、入力例1だと以下のようになっている。

以下のように値ごとに移動に必要なコスト(魔力)の累積和をいれておけば任意の値の間の必要な魔力が $O(1)$ で求める事ができる。

コード

実装時のTips

通常の累積和ではなく、飛び飛びの累積和を求める

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// 飛び飛びの累積和
int main() {
  ll h, w, d;
  cin >> h >> w >> d;
  const int n = h * w;
  vector<int> a(n);
  unordered_map<int, pair<int, int>> p;  // {値: 座標}
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      ll v;
      cin >> v;
      p[v] = {i, j};
    }
  }
  vector<int> sm(n + 1);  // iまでの累積和
  for (int i = 1 + d; i <= n; i++) {
    ll j = i - d;
    sm[i] = sm[j] + abs(p[i].first - p[j].first) + abs(p[i].second - p[j].second);
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    ll l, r;
    cin >> l >> r;
    cout << sm[r] - sm[l] << endl;
  }
}

ABC 089 | D - Practical Skill Test

問題

解法

コード

参考

Discussion