ARC024 D バス停

問題ページ

解法

ある列の格子点全てにバス停を置くと、任意のその列を跨いだ左右間の移動が可能となり、かつ総移動距離がマンハッタン距離と等しくなるようにできる。よって、左右独立に考えることができるようになるため、分割統治でこの問題を解くことができる。実際に全ての格子点にバス停を置く必要はなく、バス停がある行にだけ置けば十分である。これをバス停がある列を順に並べた時にちょうど真ん中の列に対して行い、左右それぞれの区域でも同じことを再帰的に行う。これでバス停を置く個数がおよそNlogN個となり、個数の制約をクリアできる。

実装

提出コード - https://atcoder.jp/contests/arc024/submissions/6750348

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;

vector< pair<int, int> > v, ans;
set< pair<int, int> > st;

void solve(int l, int r){
    if(r - l <= 1){
        return;
    }

    int m = (l + r) / 2;
    for(int i = l ; i < r ; ++i){
        if(v[i].first != v[m].first && v[i].second != v[m].second && !st.count({v[m].first, v[i].second})){
            ans.emplace_back(v[m].first, v[i].second);
            st.insert(ans.back());
        }
    }

    solve(l, m);
    solve(m + 1, r);

    return;
}

int main(){
    int n;
    cin >> n;

    for(int i = 0 ; i < n ; ++i){
        int x, y;
        cin >> x >> y;
        v.emplace_back(x, y);
        st.insert(v.back());
    }
    sort(v.begin(), v.end());

    solve(0, n);

    cout << ans.size() << endl;
    for(auto x : ans){
        cout << x.first << " " << x.second << endl;
    }

    return 0;
}