2023-11-27

AtCoder ABC 330 F - Minimize Bounding Square (青色, 525 点)

AtCoder AtCoder525点 ABC-F 青色diff 二次元平面上のN点の問題制約条件:正方形領域二分探索二分探索:最適化問題を判定問題に帰着する操作操作をK回まで行える最大スコア操作:点を移動する中央値(メディアン)に関する問題絶対値やminを扱う問題区分線形関数全部混ぜて解くそのまま覚えたいシンプル設定の中堅以上の典型問題 x軸とy軸について独立に考えてよい Greedy:各要素について独立に考えてよい Greedy 最適化問題

すごく典型盛り合わせな教育的問題！

問題へのリンク

問題概要

二次元平面上に $N$ 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を $K$ 回まで行える。

$N$ 個の点の中から 1 個選ぶ
その点を上下左右のいずれかに 1 マス動かす

操作後において、 $N$ 個の点を正方形で囲う。その正方形の一辺の長さの最小値を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$
$0 \le K \le 4 \times 10^{14}$

考えたこと

全体としては二分探索がバッチリはまる。座標値の差の最大値を $M$ として、次の判定問題を $O(\log M)$ 回解くことで求められる。

$N$ 個の点を $K$ 回以内の移動によって、正方形の一辺の長さを $l$ 以下にできるかどうかを判定せよ

具体的な判定方法としては、正方形の一辺の長さを $l$ 以下にするまでの最小ステップ回数を求めて、それが $K$ 以下かどうかを判定することにしよう。

ここでさらに重要な考察として、x 座標と y 座標を独立に求めて、それらの最小ステップ数を合計すればよいということだ。

有名問題に帰着

こうして、我々は次の問題を解けば良いこととなった。

一直線上に $N$ 個の点があって、各点の座標は $A_{1}, A_{2}, \dots, A_{N}$ がある。

一直線上に長さが $l$ の棒を配置する。各点をこの棒の内部におさまるように移動する距離の総和の最小値を求めよ。

$l = 0$ のときは非常によく知られている。それはすなわち、数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられて

$|x - A_{1}| + |x - A_{2}| + \dots + |x - A_{N}|$

の最小値を求める問題だ。これは数列 $A$ のメディアンを求めれば良い。これと同様の考察で解ける。

区分線形関数を考える

例として、 $A = (0, 4, 6)$ , $l = 3$ の場合を考えてみよう。 $x$ を「棒の左端の座標」として、 $x$ を動かしたときの移動距離は下図のような区分線形関数となる。

$x$ が十分小さいときは、 $x$ を右に 1 動かすと $N$ 個の点との距離がすべて 1 ずつ縮まるため、傾きは $-N$ である。その後は

区間の左端がある点を通過する (ある $i$ について $x = A_{i}$ となる瞬間)
区間の右端がある点を通過する (ある $i$ について $x = A_{i} - l$ となる瞬間)

というイベントが起こるたびに、傾きが 1 ずつ増えていくことがわかる。このうち、傾きが 0 になる部分が求める最小値だ。

つまり、 $x$ が $2N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}, A_{1} - l, A_{2} - l, \dots, A_{N} - l$ のメディアン (中央値) であるとき、求める移動距離が最小となる。

メディアンを求めるためには、 $2N$ 個の整数をソートしてもよいが、

$A_{1}, A_{2}, \dots, A_{N}$ がソート済み配列である
$A_{1} - l, A_{2} - l, \dots, A_{N} - l$ がソート済み配列である

ということを活かして、もっと高速にできる。ちょうどマージソートの「マージ」の部分をやればよいのだ。 $O(N)$ の計算量でできる。

全体として、計算量は $O(N(\log N + \log M))$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using pint = pair<int, int>;
using pll = pair<long long, long long>;

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    
    // (A1, ..., AN) と (A1 - x, ..., AN - x) をマージしながらソート (O(N))
    // そしてメディアンを答える
    auto calc = [&](const vector<long long> &A, long long x) {
        vector<long long> B(N);
        for (int i = 0; i < N; ++i) B[i] = A[i] - x;
        
        // ソートされた 2N 個の配列を作る
        vector<long long> v;
        int i = 0, j = 0;
        while (i < N || j < N) {
            if (i == N || (j < N && A[i] > B[j])) v.push_back(B[j++]);
            else v.push_back(A[i++]);
        }
        
        // メディアンに揃える
        long long median = v[N];
        long long res = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] < median) res += median - A[i];
            else if (A[i] > median + x) res += A[i] - (median + x);
        }
        return res;
    };

    // 二分探索
    long long low = -1, high = 1LL<<32;
    while (high - low > 1) {
        long long mid = (high + low) / 2;
        if (calc(X, mid) + calc(Y, mid) <= K) high = mid;
        else low = mid;
    }
    
    cout << high << endl;
}