🕒 2020/10/08 🔄 2024/10/09

ABC045D/ARC061B すぬけ君の塗り絵を解きました

🐳

問題概要

縦 $H$、横 $W$ のマス目のうち、$N$ 箇所を黒く塗った。それぞれの 3x3の連続するマス目に対して黒いマスの数を数える。黒いマスが $j$ 個となる3x3のマス目はいくつあるか、各 $j$ に対して答えなさい。

$3\\leqq H, W\\leqq 10^9$, $N$ は $10^5$ 以下

各3x3のマスを1個1個考えていくと間に合わないので、早く数える方法を考える。黒くないマスばっかりなので、黒いマスを中心に考えればいい。

黒いマスをmapで管理する。また、黒いマスが右下にくるような3x3もmapに入れておく。

次に、mapに入っている各キーに対して、そのセルが左上に来るような3x3のマスをmapから探す。なければ黒くない。あっても黒いかどうかはわからないけど、値を見ればわかる。

黒いマスが0個のケースは、全体から1以上のを引けばおしまい。

考察ふわふわな状態で実装し始めたせいで、mapに値を入れていく際、黒いマスだけを対象にしてしまっていた。ここをなおすと、後半で、「mapにキーがあったら黒いマス」という前提を置いていたので、そこも書き直さないといけなくなって、イマイチだった。