はまやんはまやんはまやん

hamayanhamayan's blog

Dist Max 2 [AtCoder Beginner Contest 215 F]

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

https://atcoder.jp/contests/abc215/tasks/abc215_f

前提知識

解説

https://atcoder.jp/contests/abc215/submissions/25244049

二分探索と尺取り法の知識はこれ以降の解説を理解するのに必須であるので、
分かっていない場合は学んでくることを勧める。

まずは二分探索を思いつく必要がある。
最小値の最大値とか、その逆とかは二分探索っぽいみたいな話があるが、今回もそれにちょっと似ている感じがする。
それもあって、二分探索から考えてみると、解法にたどり着いた。
この部分がまず1つ目の山となる。

二分探索

どういった条件で考えるかというと、

check(lim) := 異なる2つの点の距離の最大値がlim以下であるか

というのを判定問題として二分探索をしていくことにする。
仮に答えが10であれば、

...
check(8) = false
check(9) = false
check(10) = true
check(11) = true
...

のようになるので、境界線の上側が答えになる。

判定条件

「異なる2つの点の距離の最大値がlim以下であるか」というのは、このままだとあまり意味のある条件には見えないような感じがする。
なので、言い換えよう。

「異なる2つの点の距離の最大値がlim以下であるか」
というのは、「全頂点間で min (xの差, yの差)≦lim を満たす」である場合に満たされることになる。
minというのはちょっと面倒なので、もう少しばらすと、
「全頂点間で xの差≦lim または yの差≦lim を満たす」
となる。

正直、高速に計算できそうなやつに寄せて作っている条件なので、あまり納得感がないかもしれない。
この判定を高速に行っていく。

2軸を1軸に

x軸とy軸でそれぞれ考えるのは大変なので、どちらかでも何とかしたいものである。
今回の点の集合は特に順番に意味はないので、ソートをしても問題ない。
あらかじめx座標でソートしておこう。
こうすることで、距離の区間に変換しやすくなる。

具体的にはとある点iについてxの差がlim以下である点を考えると、ちょうどiを含む区間になることが分かるだろう。
とある点iについて、区間[L,R)についてはxの差がlim以下であるとすると、この区間については条件を満たすことになる。
逆に[0,L)の区間と、[R,N)の区間についてはxの差がlimより大きいことになる。
つまり、この区間に含まれる点はすべてyの差がlim以下である必要がある。
なので、この区間に含まれる点において、yの差がlimより大きいものがあるかを探すことで判定関数がfalseと返すかを決めることができる。

このように片方をソートすることで、問題を区間に変換することができ、区間内ではもう片方だけを考慮するだけで良くなったりする。
平面走査と呼んでもいい（し、まんまか）。

実装

すべての点iについて区間[L, R)を特定する方法として、尺取り法を用いる。
これはLもRもiが増えていくたびに広義単調増加していくのはイメージ付くだろう。
よって、尺取り法によって高速に区間[L, R)を特定できる。

[0,L)の区間と、[R,N)の区間についてはxの差がlimより大きいものがあるかを判定する方法について考える。
y[i]と最も距離がありそうな点というのは、その区間に含まれる最小のy座標と、最大のy座標となる。
なので、その区間において、y座標の最大値と最小値が得られればいい。
自分はSparseTableを用いた。これはざっくり言うと高速なセグメントツリーである。
取得がO(1)で行える。SparseTableを用いても、O(Nlog最大値)みたいな感じでNも2*105なので、セグメントツリーのO(Nlog2N)が
ちょっと怖くて、SparseTableにした。
だが、今思えば、先頭からと末尾からの区間なので、累積和としてmin/maxを用意するだけでよさそうである。

これで2つの区間の最大値と最小値を持ってきてy[i]との距離を測ってlimを超えていれば判定関数はfalseを返す。

int N;
vector<pair<int, int>> points;
SparseTableMin<int> stmin;
SparseTableMax<int> stmax;
//---------------------------------------------------------------------------------------------------
bool check(int lim) {
    int L = 0, R = 0;
    rep(i, 0, N) {
        while (R < N && points[R].first - points[i].first <= lim) R++;
        while (lim < points[i].first - points[L].first) L++;

        int ma = max(stmax.get(0, L), stmax.get(R, N));
        if (0 <= ma && lim < abs(ma - points[i].second)) return false;

        int mi = min(stmin.get(0, L), stmin.get(R, N));
        if (mi < inf && lim < abs(mi - points[i].second)) return false;
    }

    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        points.push_back({ x, y });
    }
    sort(all(points));
    
    vector<int> dic;
    rep(i, 0, N) dic.push_back(points[i].second);
    stmin.init(dic);
    stmax.init(dic);

    int ng = -1, ok = inf;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}