AtCoder ABC 361 G - Go Territory (4D, ？色, 600 点)

方針を決めるのが大変な問題。

• 問題へのリンク

問題概要

二次元平面上の 個の格子点に碁石が置かれている。

このとき、碁石によって囲われている格子点の個数を求めよ。より正確には、「その空き格子点から上下左右の空き格子点への移動を繰り返して点 (-1, -1) に移動できないような空き格子点」の個数を求めよ。

制約

• 
• 

考えたこと

僕自身は、領域を管理するような BFS をしようとして実装に詰まっていた。その後、この公式解説を学んだ。

各 座標を固定して、y 座標が 0 から 200000 までの「 の長方形」を考える。この長方形を碁石によって分断して得られる長方形を考える (下図は公式解説より)。

この長方形を頂点として、縦に隣接している長方形間に辺を張ったグラフを考えて、BFS をすればよい。ここで計算量解析が重要だ。

碁石を 1 個置くごとに、

• 頂点の個数は高々 1 個しか増えない
• 辺の本数は高々 2 本しか増えない

ということが言える。したがって、 としたとき、頂点数も辺数も となる。よって、この BFS の計算量は と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
using Rect = array<int, 4>;
const int MAX = 210000;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<vector<int>> go(MAX);
    for (int i = 0; i < N; ++i) {
        int X, Y;
        cin >> X >> Y;
        ++X, ++Y;
        go[X].push_back(Y);
    }
    for (int x = 0; x < MAX; ++x) {
        sort(go[x].begin(), go[x].end());
        go[x].push_back(MAX);
    }
    
    // 長方形の短冊を抽出
    vector<Rect> rects;
    vector<vector<Rect>> tate(MAX);
    for (int x = 0; x < MAX; ++x) {
        int prev = 0;
        for (auto v : go[x]) {
            int id = rects.size();
            rects.push_back(Rect({x, prev, v, id}));
            tate[x].push_back(Rect({x, prev, v, id}));
            prev = v+1;
        }
    }
    
    // グラフを構築
    vector<vector<int>> G(rects.size());
    auto adj = [&](Rect p, Rect q) -> bool { return min(p[2], q[2]) - max(p[1], q[1]) >= 1; };
    for (int x = 0; x + 1 < MAX; ++x) {
        int a = 0, b = 0;
        while (a < tate[x].size() && b < tate[x+1].size()) {
            int u = tate[x][a][3], v = tate[x+1][b][3];
            if (adj(tate[x][a], tate[x+1][b])) G[u].push_back(v), G[v].push_back(u);
            if (tate[x][a][2] > tate[x+1][b][2]) ++b;
            else if (tate[x][a][2] < tate[x+1][b][2]) ++a;
            else ++a, ++b;
        }
    }
    
    // BFS
    vector<int> dp(rects.size(), -1);
    queue<int> que;
    que.push(0);
    dp[0] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto v2 : G[v]) {
            if (dp[v2] == -1) {
                dp[v2] = dp[v] + 1;
                que.push(v2);
            }
        }
    }
    long long res = 0;
    for (int v = 0; v < rects.size(); ++v) {
        if (dp[v] == -1) res += rects[v][2] - rects[v][1];
    }
    cout << res << endl;
}