ARC061 D すぬけ君の塗り絵 / Snuke's Coloring

問題概要

縦 $H$ マス横 $W$ マスの盤があり、すべて白く塗られている。
この状態から $N$ マスを黒く塗りつぶした。 $i$ 番目の黒いマスは上から $a_i$ 行目で左から $b_i$ 列目のマスである。

$0 \le j \le 9$ を満たす全ての $j$ について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど $j$ 個あるものの個数を求めよ。

制約
$2 \le H, W \le 10^9$
$1 \le N < min(10^5, H \times W)$
$1 \le a_i \le H$
$1 \le b_i \le W$

解法

マス $(i, j)$ を黒く塗ったとき、3行3列の連続するマス目のうち関係するのは、中央が $(i-1, j-1), (i-1, j), (i-1, j+1),$ $(i, j-1), (i, j), (i, j+1),$ $(i+1, j-1), (i+1, j), (i+1, j+1)$ であるようなもの（で、かつ盤の中に完全に含まれるもの）である。また、1マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々9個であり、 $N$ マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々 $9N$ 個である。

よって、高々 $9N$ 個を全列挙して数え上げれば、 $1 \le j \le 9$ を満たす全ての $j$ について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど $j$ 個あるものの個数は求められる。
盤の中に完全に含まれるすべての3行3列の連続するマス目は $(H-2)(W-2)$ 個なので、 $j = 0$ のときは、「 $(H-2)(W-2) -$ ( $1 \le j \le 9$ の時の答えの総和) 」が答えとなる。

Submission #2152583 - AtCoder Regular Contest 061

足跡-sokuseki-

りかの日進月歩の記録

ARC061 D すぬけ君の塗り絵 / Snuke's Coloring

問題概要

解法