【典型90問】036 - Max Manhattan Distance（★5）

atcoder.jp

この問題は下の問題とほぼ同じだった。
atcoder.jp

↓自分の記事 nizi-24.hatenablog.com

解法

絶対値によってiとjが分かれている問題は、絶対値を外してiとjを独立に計算すると良いことが多い。

$ x_i ≧ x_j $としても一般性を失わない($ x_i < x_j $のときはiとjをswapすればよい) ため、この条件を元に絶対値を外してみると、

max($ | (x_i+y_i) - (x_j+y_j) | $, $ | (x_i-y_i) - (x_j-y_j) | $ )

という風に式変形できる。
(式変形の詳細はDist Maxの記事の中で紹介しているけんちょんさんの記事がわかりやすい。)

この問題ではiとjのどちらかが固定されることになるので、x' = x + y, y' = x - yとし、x'の最大値をx'M、最小値を x'mとすると、(y'も同じようにする)

ans = max(| x' - x'M |, | x' - x'm |, | y' - y'M |, | y' - y'm |)

となる。

実装

void solve(long long N, long long Q, std::vector<long long> x, std::vector<long long> y, std::vector<long long> q) {
    vector<pair<ll, ll>> dist1(N), dist2(N);
    REP (i, N) {
        dist1[i] = {x[i] + y[i], i};
        dist2[i] = {x[i] - y[i], i};
    }
    ALL(sort, dist1);
    ALL(sort, dist2);

    REP (j, Q) {
        int i = q[j]-1;
        ll mx = max(abs(x[i] + y[i] - dist1[0].first), abs(x[i] - y[i] - dist2[0].first));
        chmax(mx, max(abs(x[i] + y[i] - dist1[N-1].first), abs(x[i] - y[i] - dist2[N-1].first)));
        c(mx)
    }

}