AtCoder Regular Contest 024 D - バス停

なんとなくマラソンマッチっぽい問題だと思いました。

問題

arc024.contest.atcoder.jp

解法

解説を参考にして解きました。

AtCoder Regular Contest 024 解説 from AtCoder Inc.

www.slideshare.net

今, [xl, xr) の間で条件を満たそうとしているとします。この範囲に 1 つ以下の頂点しかない場合は, 特になにもしなくても大丈夫です。
複数の頂点がある場合は, ある頂点 xm が存在して, その xm について [xl, xm) にある頂点の数と, [xm+1, xr) にある頂点の数が, 両方共 [xl, xr) にある頂点の数の半分以下になります。
この xm 上にバス停をたくさん配置すると, [xl, xm) から [xm+1, xr) 側には最短距離で行けるようになります。よって, あとは [xl, xm) と [xm+1, xr) に問題を分けて考えれば良いことになります。このようにして分割統治が使えます。

毎回頂点数が半分以下になるので, dfs の深さは O(log N), 各 dfs の計算量は O(N) 程度(下では set を使っているので O(NlogN)) なので, 十分計算が間に合います。

const int MAXN = 1010;
int N;

vector<int> Y[MAXN];

vector<pii> ans;

void dfs(int xl, int xr) {
    int cnt = 0;
    set<int> S;
    for (int x = xl; x < xr; x++) {
        cnt += Y[x].size();
        for (int y : Y[x]) S.insert(y);
    }
    if (cnt <= 1) return;
    int xm = xl, left = 0;
    for (; xm < xr; xm++) {
        left += Y[xm].size();
        if (left*2 >= cnt) break;
    }
    for (int y : Y[xm]) S.erase(y);
    for (int y : S) ans.emplace_back(xm, y);
    dfs(xl, xm);
    dfs(xm+1, xr);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        Y[x].push_back(y);
    }
    dfs(0, 1001);
    cout << ans.size() << endl;
    for (auto p : ans) cout << p.first << " " << p.second << endl;
    return 0;
}