Codeforces #249 Div2 D. Special Grid

これはなかなか面白い問題。
http://codeforces.com/contest/435/problem/D

問題

NxM個の長方形状に等間隔に点が並んでおり、各点は白か黒である。
これらの点は、隣接する上下左右の点同士が線でつながれている。
また、これらの線で構成される正方形に対し、さらにその対角線状にある点同士も線でつなぐ。

これらの線で構成された三角形のうち、辺上の点が白色だけであるものの数を答えよ。

解法

線を結んで生成できる三角形は垂直二等辺三角形であり、３辺のうち一辺は点が配置された格子と平行である。

事前に白点が上下および左右方向に何個連続するか累積和を求めておく。

各頂点から三角形の２辺を伸ばしていき、累積和を用いてその２辺の終端同士の間が白点が連続するか求めていけばよい。
O(N*M*(N+M))でちょっと重いが何とか間に合う。
同じ三角形を多重にカウントしないよう注意。

以下のコードは本番のものを簡略化したもの。

int H,W;
string S[401];
int num[405][405][2];

void solve() {
	int f,i,j,k,l,x,y,x2,y2;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) S[y][x]=S[y][x]=='0';
	
	FOR(y,H) {
		FOR(x,W) num[y+1][x+1][0]=S[y][x]?(1+num[y+1][x][0]):0;//L
		FOR(x,W) num[y+1][x+1][1]=S[y][x]?(1+num[y][x+1][1]):0;//U
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) if(S[y][x]) {
		//UR,R
		for(l=1;x+l<W && y-l>=0 && S[y-l][x+l] && S[y][x+l]; l++) if(num[y+1][x+l+1][1]>=l+1) ret++;
		//DR,R
		for(l=1;x+l<W && y+l<H && S[y+l][x+l] && S[y][x+l]; l++) if(num[y+l+1][x+l+1][1]>=l+1) ret++;
		//UL,L
		for(l=1;x-l>=0 && y-l>=0 && S[y-l][x-l] && S[y][x-l]; l++) if(num[y+1][x-l+1][1]>=l+1) ret++;
		//DL,L
		for(l=1;x-l>=0 && y+l<H && S[y+l][x-l] && S[y][x-l]; l++) if(num[y+l+1][x-l+1][1]>=l+1) ret++;
		//UL,UR
		for(l=1;x-l>=0 && x+l<W && y-l>=0 && S[y-l][x-l] && S[y-l][x+l]; l++) if(num[y-l+1][x+l+1][0]>=2*l+1) ret++;
		//DL,DR
		for(l=1;x-l>=0 && x+l<W && y+l<H && S[y+l][x-l] && S[y+l][x+l]; l++) if(num[y+l+1][x+l+1][0]>=2*l+1) ret++;
		//UL,DL
		for(l=1;x-l>=0 && y-l>=0 && y+l<H && S[y-l][x-l] && S[y+l][x-l]; l++) if(num[y+l+1][x-l+1][1]>=2*l+1) ret++;
		//UR,DR
		for(l=1;x+l<W && y-l>=0 && y+l<H && S[y-l][x+l] && S[y+l][x+l]; l++) if(num[y+l+1][x+l+1][1]>=2*l+1) ret++;
	}
	cout << ret << endl;
}