AtCoder ARC #061 : D - すぬけ君の塗り絵 / Snuke's Coloring

相変わらずいまいち。
http://arc061.contest.atcoder.jp/tasks/arc061_b

問題

H*Wの白黒グリッド中、N箇所黒いマスが指定される。
H*Wのグリッド中にある3*3のマス目を列挙したとき、黒マスが0～8個のケースはそれぞれいくつあるか。

解法

3*3のマス目は(H-2)*(W-2)通り取れるが、これを全部探索するとTLEする。
3*3のマス目中に1個以上黒マスがあるのは、最初に黒マスが指定された周辺のみなのでそこだけ探索しよう。

set<pair<int,int>> S;
set<pair<int,int>> S2;
ll H,W,N;
ll A[10];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>x>>y;
		S.insert({x,y});
		FOR(j,3) FOR(k,3) S2.insert({x-j,y-k});
	}
	
	A[0]=(H-2)*(W-2);
	FORR(r,S2) {
		x = r.first;
		y = r.second;
		if(x<=0 || x+2>H) continue;
		if(y<=0 || y+2>W) continue;
		int ret=0;
		FOR(j,3) FOR(k,3) ret += S.count({x+j,y+k});
		
		A[ret]++;
		A[0]--;
		
	}
	FOR(i,10) cout<<A[i]<<endl;
	
}

まとめ

Dの割に簡単。