HackerRank Drawing Rectangles

問題文

https://www.hackerrank.com/contests/university-codesprint-4/challenges/drawing-rectangles

問題概要

グリッド内の n 個の長方形を, 列または行を削除する操作によって最小回数で全て消したい.
その最小回数と消すべき列, 行を出力せよ.
ただし長方形の x, y 座標の範囲は [0, 3e5] で, さらに全長方形の和集合の面積は 3e5以下.

解法

和集合の面積が3e5以下であることから, いずれかの長方形に含まれる任意のマスは map を持って平面走査することで列挙することができます.

あとは行と列の二部グラフを作って辺を貼れば, 最小点カバーを求める問題となります.
最小点カバーは最大流を流したあとに, その残余グラフで BFS などを行うことで求めることができるのでOK.

グラフのサイズがかなり大きいですが, 二部グラフの最大マッチングでは dinic なら O(E√V) なので間に合います.

ソースコード

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

const int INF = 1e9;

struct edge {
    int to, cap, rev;
    edge(int to_, int cap_, int rev_) : to(to_), cap(cap_), rev(rev_) {};
};

const int MAX = 3e5 + 1;

const int V = MAX * 2 + 2;

const int src = MAX * 2, syn = MAX * 2 + 1;

vector<edge> G[V];
int level[V];
int iter[V];

void add(int from, int to, int cap) {
    G[from].emplace_back(to, cap, G[to].size());
    G[to].emplace_back(from, 0, G[from].size() - 1);
}

void bfs(int s) {
    fill(level, level + V, -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = 0; i < (int)G[v].size(); i++) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < (int)G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int dinic(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        fill(iter, iter + V, 0);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> recs;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2; x2++, y2++;
        vector<int> v1 = { x1, y1, y2, 1 };
        vector<int> v2 = { x2, y1, y2, -1 };
        recs.push_back(move(v1));
        recs.push_back(move(v2));
    }
    for (int i = 0; i < MAX; i++) {
        add(src, i, 1);
        add(MAX + i, syn, 1);
    }
    sort(recs.begin(), recs.end());
    map<int, int> imo;
    for (int x = 0, id = 0; x < MAX; x++) {
        while (id < (int)recs.size() && recs[id][0] == x) {
            int l = recs[id][1], r = recs[id][2], v = recs[id][3];
            imo[l] += v; if (imo[l] == 0) imo.erase(l);
            imo[r] -= v; if (imo[r] == 0) imo.erase(r);
            id++;
        }
        int cnt = 0, pos = 0;
        for (auto& p : imo) {
            if (cnt > 0) {
                for (int y = pos; y < p.first; y++) {
                    add(x, MAX + y, 1);
                }
            }
            pos = p.first;
            cnt += p.second;
        }
    }
    int res = dinic(src, syn);
    vector<int> used(MAX * 2);
    queue<int> q;
    for (auto e : G[src]) if (e.cap > 0) {
        used[e.to] = 1;
        q.push(e.to);
    }
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        for (auto e : G[p]) if (e.to != src && e.to != syn && e.cap > 0 && !used[e.to]) {
            used[e.to] = 1;
            q.push(e.to);
        }
    }
    vector<int> xs, ys;
    for (auto e : G[src]) if (e.cap == 0 && !used[e.to]) {
        xs.push_back(e.to);
    }
    for (auto e : G[syn]) if (e.cap > 0 && used[e.to]) {
        ys.push_back(e.to - MAX);
    }
    cout << res << endl;
    cout << xs.size() << endl;
    for (int i = 0; i < (int)xs.size(); i++) {
        if (i != 0) cout << ' ';
        cout << xs[i];
    }
    cout << endl;
    cout << ys.size() << endl;
    for (int i = 0; i < (int)ys.size(); i++) {
        if (i != 0) cout << ' ';
        cout << ys[i];
    }
    cout << endl;
    return 0;
}

感想

二部グラフの最小点カバーのやり方を知らなくてコンテスト本番では解けなかったけど, 面白い問題だと思った.
あと制約が大きいせいで, これフローいけるの？ってなりがち.