AtCoder Beginner Contest 045 D - すぬけ君の塗り絵 / Snuke's Coloring

これは割とすんなり解けたかな。

from collections import Counter


def solve(H, W, N, ABs):
    total = (H - 2) * (W - 2)
    points = {}
    for a, b in ABs:
        a -= 1
        b -= 1
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                if 0 < a + i < H - 1 and 0 < b + j < W - 1:
                    d = (a + i, b + j)
                    if d not in points:
                        points[d] = 0
                    points[d] += 1
    c = Counter([v for v in points.values()])
    ans = [total - len(points)] + [c[f] if f in c else 0 for f in range(1, 10)]
    return "\n".join([str(a) for a in ans])

if __name__ == "__main__":
    H, W, N = map(int, input().split(" "))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(H, W, N, ABs))

H, Wがかなり大きいので、盤面すべてを記録する or 全3x3の正方形の走査は除外。 Nは走査がいけそうなので、各点から計算ができるかを考える。

ある点が影響を及ぼすのは高々9個のみ、つまり3x3正方形の中で0とならないものは最大でも 9 * N <= 9 * 10⁵でこれを数えていけばよい。

教訓

• (若干邪道だが)10⁹なものは初めから数えられると思わず、数えられるものから考える。
• 境界条件はやはり注意が必要。プログラムを実行せずに頭の中でちゃんと考える癖をつける。