# ABC330-F Minimum Bounding Square

https://atcoder.jp/contests/abc330/tasks/abc330_f

二分探索の適用を考える[^1]。制約より一辺の長さが$10^{9}$の正方形で必ず全ての点を囲むことができる[^2]ので、「一辺の長さが$l$の正方形で全ての点を囲うことができるか？」という判定問題を$\log_{2}(10^{9})$回行えば良い。

判定問題を言語化するとこんな感じ
ある点$(x, y)$が存在して、高々$K$回の操作によって全ての点を正方形$(x, y), (x + l, y), (x + l, y + l), (x, y + l)$の周上もしくは内部に移動させることが可能か？

これは、全ての点を正方形の内部に移動させるために必要な操作の最小回数を最小化するような$(x, y)$を発見し、この場合で操作回数の最小回数が$K$回以下であるかを確認すれば良い。

$x$軸$y$軸について独立である[^3]。$x$軸についての解き方について考える($y$軸に関しては適宜用語や変数を言い換えることによって同様に解ける)

左端$L$を決めた時、全ての点の$x$座標を$[L, L + l]$内部に移動させるために必要な操作の最小回数を$f_{(L, l)}$とすると、、$f_{(L, l)} = \sum_{i = 1}^{N} \min_{j = L}^{L + l} |x_i - j|$である。

$\min_{j = L}^{L + l}|x_{i} - j| =
\begin{cases}
L - x_{i} & \text{if}\ x_{i} < L \\
x - (L + l) & \text{if}\ x_{i} > (L + l) \\
0 & \text{else}
\end{cases}$

より、$L$より負側にある点と$L + l$より正側にある点の情報が重要となる。

ここで、$L$より負側にある点の個数を$p$、$L + l$より正側にある点の個数を$q$とする。

$f_{(L + 1, l)} = f_{(L, l)} + p - q$、$f_{(L - 1, l)} = f_{(L, l)} + q - p$が成り立つことがわかる。よって$p > q$ならば、できるだけ$L$を負側に、$p < q$ならば$L$をできるだけ正側へ移動させた方が$f_{(L, l)}$が減少することがわかる。
- 特に、$|p - q| \le 1$の時に最適な$L$があることがわかる。これは数直線上の$N$点からの距離を最小化する点が$N$の中央値に一致することと同様の議論をしている(と思う......)
- 特に、ある$L$が存在して、ある点$i$が存在して$x_{i} = L$または$x_{i} = L + l$が成り立つかつ$f_{(L, l)}$が同じ$l$の中で最小値をとることがわかる。(実装の時に利用できる)

以上の考察より、尺取り法などを用いて時間・空間計算量$O(N)$で$f_{(L, l)}$を最小化する$L$を発見することができる。また、その$L, l$における$f_{(L, l)}$も求まる。

#### 実装

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n; std::cin >> n;
    long long k; std::cin >> k;
    std::vector<int> x(n), y(n);
    for (int i{} ; i < n ; i++) std::cin >> x[i] >> y[i];
    std::ranges::sort(x);
    std::ranges::sort(y);

    std::cout << std::boolalpha;

    auto LtoR{[&](int len, const std::vector<int>& a) -> long long {
        long long L{}, R{};
        int l{}, r{};
        while (r < n and a[l] + len >= a[r]) r++;
        for (int i{r} ; i < n ; i++) R += a[i] - (a[l] + len);
        long long res{L + R};
        for ( ; l < n ; l++) {
            while (r < n and a[l] + len >= a[r]) {
                if (l) R -= a[r] - (a[l - 1] + len);
                r++;
            }
            if (l) {
                long long prev{a[l - 1] + len};
                long long diff{a[l] + len - prev};
                R -= diff * (n - r);
            }
            // std::cout << l << ' ' << r << ' ' << L << ' ' << R << std::endl;
            res = std::min(res, L + R);
            if (l + 1 < n) {
                long long diff{a[l + 1] - a[l]};
                L += diff * (l + 1);
            }
        }
        return res;
    }};

    auto RtoL{[&](int len, const std::vector<int>& a) -> long long {
        long long L{}, R{};
        int l{n - 1}, r{n - 1};
        while (l >= 0 and a[r] - len <= a[l]) l--;
        for (int i{l} ; i >= 0 ; i--) L += (a[r] - len) - a[i];
        long long res{L + R};
        for ( ; r >= 0 ; r--) {
            while (l >= 0 and a[r] - len <= a[l]) {
                if (r + 1 < n) L -= (a[r + 1] - len) - a[l];
                l--;
            }
            if (r < n - 1) {
                long long prev{a[r + 1] - len};
                long long diff{prev - (a[r] - len)};
                L -= diff * (l + 1);
            }
            // std::cout << l << ' ' << r << ' ' << L << ' ' << R << std::endl;
            res = std::min(res, L + R);
            if (r >= 0) {
                long long diff{a[r] - a[r - 1]};
                R += diff * (n - r);
            }
        }
        return res;
    }};

    auto optimize{[&](int len, const std::vector<int>& a) -> long long {
        long long l{LtoR(len, a)};
        // std::cout << "----" << std::endl;
        long long r{RtoL(len, a)};
        // std::cout << l << ' ' << r << std::endl;
        return std::min(l, r);
    }};


    auto f{[&](int len) -> bool {
        long long v{};
        v += optimize(len, x);
        v += optimize(len, y);  
        return v <= k;
    }};

    if (f(0)) {
        std::cout << 0 << '\n';
    }
    else {
        int ans{zawa::BinarySearch((int)1e9 + 50, 0, f)};
        std::cout << ans << '\n';
    }
}

#### 感想

なかなかに添字が難しかった。本番は想定解の貪欲法で通した人が多かったのかな。

#### update

[^1]: 長さ$l$の正方形によって全ての頂点を囲うことができるような正方形の置き方と点への操作の仕方が存在すると仮定する。任意の正整数$v$について、長さ$l + v$の正方形で全ての頂点を囲うことができる。なぜなら、点に同じ操作をした上で長さ$l$の正方形を含むように長さ$l + v$の正方形を置いた場合、全ての点を囲うことに成功しているからである。

[^2]: 明らかに$(0, 0), (10^9, 0), (10^9, 10^9), (0, 10^9)$を四隅とする正方形は一回も操作を行わずとも全ての点を囲うことができている。

[^3]: 操作の性質を観察する。点$k$の座標$(x, y)$を$(x - 1, y)$もしくは$(x + 1, y)$に移動した場合は$y$軸に関してはどの点も移動しておらず、反対に$(x, y - 1), (x, y + 1)$に移動した場合は$x$軸についてどの点も移動していない。一回の操作で$x$軸に関する問題、$y$軸に関する問題両方同時に影響を与えることは無い。