ARC061 D すぬけ君の塗り絵

所見

制約がやばそうな時はやばくなさそうな制約に目をつける。
今回は特に迷わなかった(故に得たものは少ない)のに考えるのに10分、実装に20分かけており虚無。何食ったらじっそうはやくなるんですか

問題概要

HWのグリッドのうちNマスを黒く塗る。グリッドの33のマスのうち、中が0～9個塗られているものの個数をそれぞれ答えよ。

取った方針

H,Wがそれぞれ10⁹なので盤面を全部持つこともマス目に対して全部何か計算をすることも不可能。
Nが10⁵なので、そこから攻めることを考える。
一つのマスが黒く塗られたとき、影響があるのはそのマスとその周囲8マスを中心とする3*3の領域のみ。
なので、map<pair<int,int>, int>を用意して、塗られたマスに対して影響のあるキーの値をインクリメントしていけばよい。
最悪mapにN個のデータを挿入するのにNlogNであるので、N=10⁵なら十分間に合う。

正しい方針

同上

得られた知見

・制約から使える手法を逆算する
・特に、とてもでかいが疎なグリッドや行列が与えられるときはデータがある部分にのみ注目する。

解くのに必要な要素

・計算量から使える手法を読むテク
・std::mapの使い方

周辺調査によって得られた知見

・特になし