💬

ABC 178 | E - Dist Max

2 min read

問題

https://atcoder.jp/contests/abc178/tasks/abc178_e

解法

i,jの組み合わせにおいてmax (|x_i - x_y| + |y_i - y_j|)を求める問題である。
貪欲にやるとO(N^2)かかりN \leq 2 \times 10^5よりTLEしてしまう。
絶対値内でi, jが結びついているのでi, jをそれぞれ独立に計算できないか式展開をする。

|a| = a または -aなので|x_i-x_y| + |y_i-y_j|は以下に展開できる。

 \begin{aligned} (x_i - x_j) + (y_i-y_j) &= (x_i + y_i) - (x_j + y_j) \\\\ (x_i - x_j) - (y_i-y_j) &= (x_i - y_i) - (x_j - y_j) \\\\ -(x_i - x_j) + (y_i-y_j) &= -(x_i - y_i) + (x_j - y_j) \\\\ -(x_i - x_j) - (y_i-y_j) &= -(x_i + y_i) + (x_j + y_j) \\\\ \end{aligned}

プラスの項は大きく、マイナスの項は小さくできればよい。i, j独立にx+yx-yを求めソートし、それぞれ最大から最小を引いて、その最大値を求めれば答えとなる。

コード

#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 n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  // xi + yiを格納
  vector<int> a(n);
  // xi - yiを格納
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    a[i] = x[i] + y[i];
    b[i] = x[i] - y[i];
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  int ans = 0;
  ans = max(ans, a[n - 1] - a[0]);
  ans = max(ans, b[n - 1] - b[0]);

  cout << ans << endl;
}

マンハッタン距離について

とある点から距離3でいける点をプロットすると以下のようになる。

45度傾いた正方形の範囲内なら移動することができる。

とある点からとある点までの距離は上記のように表せて、max(a, b)が点間のマンハッタン距離になる。

45度傾いた座標系を扱えればマンハッタン距離を楽に扱える。

(x, y)を45度傾けた座標を(x', y')とすると以下になる。

\begin{pmatrix}x' \\ y'\end{pmatrix} = \dfrac{1}{\sqrt{2}} \begin{pmatrix}x - y \\ x + y\end{pmatrix}

これは解法ででてきたx+yx-yである。\dfrac{1}{\sqrt{2}}を無視すると max(|x_1' - x_2'|, |y_1' - y_2'|)を求めていたので45度傾けた座標で求めていたのと同じことだったのである。

参考

https://atcoder.jp/contests/abc178/tasks/abc178_e/editorial

https://kagamiz.hatenablog.com/entry/2014/12/21/213931

Discussion

ログインするとコメントできます