AtCoder ABC 385 D - Santa Claus 2 (1Q, 緑色, 425 点)

難しくはないけど、重たい！　順序付き set の練習問題。

• 問題へのリンク

問題概要

制約

• 

考えたこと

順序付き set を上手く使う問題。この問題では、次の操作を実現したくなる。ここで、集合 は、初期状態では問題文で与えられる 個の家の座標を格納することを想定している。

---

二次元平面上のいくつかの点からなる集合 を考える。

• 操作 1：2 点 を結ぶ横方向の線分上にある点のうち、 に属する x 座標が最小の点の座標を求める（なければその旨を報告する）
• 操作 2：2 点 を結ぶ縦方向の線分上にある点のうち、 に属する y 座標が最小の点の座標を求める（なければその旨を報告する）
• 操作 3： から点 を削除する

---

これらの処理を高速にこなせれば、問題文で示されたサンタクロースの移動は実装できる。

たとえば、サンタクロースが左方向に動いて、座標が から になるとする。このとき、次のようにすればよい。

---

• 2 点 を結ぶ横方向の線分上に、集合 に含まれる点が存在する限り、以下のことを行う：
  • その線分上の、集合 に含まれる x 座標が最小の点を求める（操作 1）
  • から、その点を削除する（操作 3）

---

他の方向の移動についても、同様に考えられる。

縦方向と横方向に、順序付き集合をもつ

今回の問題のように、二次元の情報を管理する上で典型的な手法がある。それは、横方向の情報と縦方向の情報を管理することだ。今回の場合、次の 2 つのデータをもつことが考えられる（C++）。

---

• map<int, set<int>> 型の変数 xy
  • xy[x] は、x 座標が であるような点の順序付き集合を表す
• map<int, set<int>> 型の変数 yx
  • yx[y] は、y 座標が であるような点の順序付き集合を表す

---

このデータを適切に持てば、上記の 3 種の操作は次のように実現できる。

操作 1：横方向の線分上の、残っている点のうち x 座標が最小の点を求める

線分の左端を 、右端を とする。C++ であれば、このとき、

xy[y].lower_bound(l)

によって、y 座標が である残っている点のうち、 座標が 以上の範囲で最小のものが求められる。もし、そのようなものが存在しないか、存在しても より大きい場合には、線分上には点が残っていないと言える。

操作 2：縦方向の線分上の、残っている点のうち y 座標が最小の点を求める

線分の下端を 、上端を とする。C++ であれば、このとき、

yx[x].lower_bound(b)

によって、x 座標が である残っている点のうち、 座標が 以上の範囲で最小のものが求められる。もし、そのようなものが存在しないか、存在しても より大きい場合には、線分上には点が残っていないと言える。

操作 3：点 を削除する

これは単純に

• xy[x].erase(y)
• yx[y].erase(x)

を実行すればよい。

まとめ

上記によって、各操作は の計算量で実行できる。

操作 1, 2 が行われる回数は高々 回（点が初期状態で 個しかないため）であり、操作 3 が行われる回数も高々 回であるから、全体の計算量は と評価できる。

コード

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

int main() {
    long long N, M, X, Y, sx, sy, C, res = 0;
    char D;
    cin >> N >> M >> sx >> sy;
    map<int, set<long long>> xy, yx;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        xy[X].insert(Y);
        yx[Y].insert(X);
    }

    // 点 (x, y) を削除する関数
    auto del = [&](long long x, long long y) -> void {
        if (!xy[x].count(y) || !yx[y].count(x)) return;
        res++;
        xy[x].erase(y);
        yx[y].erase(x);
    };

    // D 回の移動
    for (int i = 0; i < M; i++) {
        cin >> D >> C;
        long long x2 = sx, y2 = sy;
        if (D == 'U') y2 += C;
        else if (D == 'D') y2 -= C;
        else if (D == 'L') x2 -= C;
        else x2 += C;

        if (sy == y2) {
            // x 軸方向の移動の場合
            long long left = min(sx, x2), right = max(sx, x2);

            // 区間 [left, right] 上の点をすべて削除する
            if (yx.count(sy)) {
                while (true) {
                    auto it = yx[sy].lower_bound(left);
                    if (it == yx[sy].end() || *it > right) break;
                    del(*it, sy);
                }
            }
        } else {
            // y 軸方向の移動の場合
            long long bottom = min(sy, y2), top = max(sy, y2);

            // 区間 [bottom, top] 上の点をすべて削除する
            if (xy.count(sx)) {
                while (true) {
                    auto it = xy[sx].lower_bound(bottom);
                    if (it == xy[sx].end() || *it > top) break;
                    del(sx, *it);
                }
            }
        }

        // 場所を更新
        sx = x2, sy = y2;
    }
    cout << sx << " " << sy << " " << res << endl;
}