TopCoder SRM 616 Div2 Hard TwoLLogo

Div2 HardはDiv1 Hardを面白い形で条件を緩めたもの。
Div1 Hardは難しいけど、こちらはそこまででもない。
http://community.topcoder.com/stat?c=problem_statement&pm=13069

問題

二次元グリッド上で白マスと黒マスがある。
ここで白マスだけを使って"L"の文字を重ならないように2個配置したい。
そのような配置の仕方は何通りあるか。

解法

"L"字の左下のマスを総当たりし、"L"字のペアごとに数を求める。
包除原理の考え方から、まずは重なりを無視してそれぞれの左下マスから生成できるL字の組み合わせを掛け合わせる。
そこから重なるケースを引けばよい。
グリッドサイズ1辺をNとするとO(N^4)なので余裕。

class TwoLLogo {
	public:
	ll wid[31][31];
	ll hei[31][31];
	vector<pair<int,int> > OK;
	
	ll cross(int a,int b) {
		int ax=OK[a].first;
		int ay=OK[a].second;
		int bx=OK[b].first;
		int by=OK[b].second;
		ll aw=wid[ay][ax];
		ll ah=hei[ay][ax];
		ll bw=wid[by][bx];
		ll bh=hei[by][bx];
		
		if(ax==bx && by-bh<ay) return aw*bw*ah*(bh-(by-ay)+1);
		if(ay==by && ax+aw>=bx) return ah*bh*bw*(aw-(bx-ax)+1);
		if(ax<bx && ay<by && ax+aw>=bx && by-bh<=ay) return ah*bw*(aw-(bx-ax)+1)*(bh-(by-ay)+1);
		
		return 0;
	}
	
	long long countWays(vector <string> grid) {
		int H,W,x,y,z;
		H=grid.size();
		W=grid[0].size();
		OK.clear();
		
		MINUS(wid);
		MINUS(hei);
		FOR(y,H) for(x=W-1;x>=0;x--) if(grid[y][x]!='#') wid[y][x]=wid[y][x+1]+1;
		FOR(x,W) FOR(y,H) if(grid[y][x]!='#') hei[y][x]=((y>0)?hei[y-1][x]:-1)+1;
		FOR(y,H) FOR(x,W) if(wid[y][x]>0 && hei[y][x]>0) OK.push_back(make_pair(x,y));
		
		ll ret=0;
		FOR(x,OK.size()) for(y=x+1;y<OK.size();y++) {
			
			ret+=wid[OK[x].second][OK[x].first]*hei[OK[x].second][OK[x].first]*
			wid[OK[y].second][OK[y].first]*hei[OK[y].second][OK[y].first];
			ret-=cross(x,y);
		}
		return ret;
	}
};

まとめ

こういうDiv1とDiv2の分け方は珍しいな。