ABC045D/ARC061B すぬけ君の塗り絵 を解きました
🐳
これを解きました：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にキーがあったら黒いマス」という前提を置いていたので、そこも書き直さないといけなくなって、イマイチだった。