Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC015-C 「Nuske vs Phantom Thnook」 (700)

出るかっ......!そんな発想......!!

問題リンク

概要

青と白に塗られた N \times Mのグリッドがある。 (入力では「 S_{i, j} = 1 \Leftrightarrow (i, j)は青マス」なる文字列によって情報が与えられる。)

このグリッド中の任意の2つの青マスについて、青マスのみを通って片方からもう片方へ辿るルートは高々1通りである。

このとき、以下のクエリを Q個処理せよ。

  • クエリは4つの整数 x_1, y_1, x_2, y_2からなる。
  •  (x_1, y_1) (x_2, y_2)を対頂角とするグリッド内の長方形領域について、領域内の青マスの連結成分数を出力せよ。

制約

  •  1 \leq N, M \leq 2 \times 10^3
  •  1 \leq Q \leq 2 \times 10^5
  •  1 \leq x_1 \leq x_2 \leq N
  •  1 \leq y_1 \leq y_2 \leq M

解説

まず問題文に露骨に書かれている「2つの青マスの行き来できるルートは高々1通り」から、

  • 青マスを頂点
  • 隣接する青マスの間に辺を張る

ことによってできるグラフは明らかに森である。

そこから、「領域外の頂点を消せば各木が分解されるから、それをなんとか数えられないかな〜」という方針で1時間ほど考えるが諦める。

さらにTwitterで「木でないとこの問題は成立しない」「分解するって方針は多分無理」(意訳)といったヒントを貰うも、やはり思いつかない。 (ヒントを教えてくださったtempuraさん、ありがとうございました。)

このままでは一生思いつかないと察して、ついにeditorialの頭の方だけちら見することを決意。そしてこんな文面が目に入ってきた。

さて、森の各連結成分である木は、頂点数が辺数より 1 だけ大きいという性質を持っています。 すなわち、各クエリに対する答えは、その領域の頂点数 − 辺数、すなわち黒マスの数から、黒マスが隣接する箇所の数を引いたものになります。

発想の美しさに思わずため息が出た。そりゃ思いつかない。

ここまでくれば後は実装するだけだ。頂点数と辺数に関する二次元累積和を作ればいい。

頂点の方はやるだけなのだが辺の方は1つの変数だけではどうにも上手くいかない。これは「横の辺」と「縦の辺」で別々に変数を作ることで無事解決できた。

実装例

#include <iostream>
#include <string>

using namespace std;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;

    string S[N];
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }

    int vcnt[N + 1][M + 1];
    fill(vcnt[0], vcnt[N + 1], 0);
    // vcnt[i][j] = (1, 1)~(i, j)中の青マスの数
    // vcnt[i][0] = vcnt[0][j] = 0

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            // indexのズレに注意
            vcnt[i + 1][j + 1] = vcnt[i][j + 1] + vcnt[i + 1][j] - vcnt[i][j] + (S[i][j] == '1');
        }
    }

    int ercnt[N + 1][M + 1];
    fill(ercnt[0], ercnt[N + 1], 0);
    // ercnt[i][j] = (1, 1)~(i, j)中での青マスの横連結箇所数(row)

    int eccnt[N + 1][M + 1];
    fill(eccnt[0], ercnt[N + 1], 0);
    // eccnt[i][j] = (1, 1)~(i, j)中での青マスの縦連結箇所数(column)

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            ercnt[i + 1][j + 1] = ercnt[i][j + 1] + ercnt[i + 1][j] - ercnt[i][j];
            ercnt[i + 1][j + 1] += (j > 0 && S[i][j] == '1' && S[i][j - 1] == '1');

            eccnt[i + 1][j + 1] = eccnt[i][j + 1] + eccnt[i + 1][j] - eccnt[i][j];
            eccnt[i + 1][j + 1] += (i > 0 && S[i][j] == '1' && S[i - 1][j] == '1');
        }
    }

    for (int q = 0; q < Q; ++q) {
        int x[2], y[2];
        for (int i = 0; i < 2; ++i) {
            cin >> x[i] >> y[i];
        }

        int v = vcnt[x[1]][y[1]] - vcnt[x[0] - 1][y[1]] - vcnt[x[1]][y[0] - 1] + vcnt[x[0] - 1][y[0] - 1];

        int e = 0;
        e += ercnt[x[1]][y[1]] - ercnt[x[1]][y[0]] - ercnt[x[0] - 1][y[1]] + ercnt[x[0] - 1][y[0]];
        e += eccnt[x[1]][y[1]] - eccnt[x[0]][y[1]] - eccnt[x[1]][y[0] - 1] + eccnt[x[0]][y[0] - 1];

        cout << v - e << endl;
    }

    return 0;
}

実装自体はARCの500点程度かなという印象。丁寧に実装しよう。

感想

  • 次類題が出たときは確実に潰す。
  • 1時間考えて無理ならeditorialをちょっと見よう。