AtCoder ABC 045 D - すぬけ君の塗り絵 (ARC 061 D) (2Q, 青色, 400 点)

グリッドが幅広いが、黒色マスの周辺でしか「3 x 3 内部に黒色マスがある」という状況が発生しないことを活用する！

• 問題へのリンク

問題概要

グリッドの各マスは白色または黒色である。 個のマスが黒色である（座標が与えられる）。

このグリッド内部の各 3 x 3 正方形領域（ 個ある）について、黒色マスの個数を数える。

について、黒色マスの個数が 個であるような 3 x 3 正方形領域の個数を求めよ。

制約

• 
• 

考えたこと

今回は 1-indexed のままで考える。（0-indexed でもよい。）

で、 であることを考えると、圧倒的に多くの 3 x 3 領域は黒色マスを含まない。よって、黒色マスが 0 個であるような 3 x 3 領域については、全体（ 個）から、黒色マスが 1, 2, ..., 9 個であるような 3 x 3 領域の個数を引くことで求めるのが良さそうである。

さて、黒色マスが 1 個以上あるような 3 x 3 領域は、そもそも「黒色マスの周辺」のみに限られることに注意しよう！！！

ここで、3 x 3 領域を「その真ん中の正方形の座標」で表すことにする。つまり、左上の 3 x 3 領域は (2, 2) と表せる。このとき、黒色マス () に対して考慮すべき 3 x 3 領域は、次の 9 個である！！

• 
• 
• 
• 
• 
• 
• 
• 
• 

これらすべてについて、黒色マスの個数を数えていけば良い。

なお、異なる黒色マスに対して、その周辺の 3 x 3 領域を数えるときに、3 x 3 領域をダブルカウントしないように注意。set<pair<int, int>> 型で管理するなどすれば大丈夫。

このとき、全体の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    long long H, W, N;
    cin >> H >> W >> N;
    set<pint> S;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        S.insert(pint(x, y));
    }

    // マス (x, y) を真ん中とする 3 x 3 マス内の黒マスの個数
    auto calc_num = [&](int x, int y) -> int {
        int num = 0;
        for (int i = x-1; i <= x+1; i++) {
            for (int j = y-1; j <= y+1; j++) {
                if (S.count(pint(i, j))) num++;
            }
        }
        return num;
    };

    // 集計
    vector<set<pint>> hist(10);
    for (auto [x, y] : S) {
        for (int i = x-1; i <= x+1; i++) {
            for (int j = y-1; j <= y+1; j++) {
                if (i-1 < 1 || i+1 > H || j-1 < 1 || j+1 > W) continue;
                hist[calc_num(i, j)].insert(pint(i, j));
            }
        }
    }
    long long zero = (H - 2) * (W - 2);
    for (auto se : hist) zero -= (long long)se.size();
    cout << zero << endl;
    for (int i = 1; i < 10; i++) cout << hist[i].size() << endl;
}