Codeforces #217 Div2. D. Broken Monitor

最初アプローチミスで時間を無駄にしまくったのが悔やまれる。
どうせ途中バグもあってpretest通っても本番通らなかったけどさ。
http://codeforces.com/contest/370/problem/D

問題

WxHの大きさのグリッド上にいくつか白いマスが与えられる。
このグリッド上に、縁の太さが1マス分の正方形を置きたい。

グリッド上のすべての白いマスが縁の上にある正方形があれば、そのうち最小のものを示せ。

解法

色々なアプローチがあるが、自分のアプローチは以下の通り。
まず、白いマスが1個だけならそのマスだけからなる正方形が答えなので自明。
白いマスが2つ以上あるなら、1辺が2以上である。

ここで、1つ白いマスを選択する。
グリッドの全マスについて、そのマスを正方形の四つ角のうちの一つと仮置きすると、選択した白いマスを通るためには正方形の大きさが一意に定まる（2セルにおけるX座標およびY座標の差の大きい方）。
あとは、その正方形の縁に全部の白マスが含まれるか調べればよい。

事前に前処理で白マスを数えておくと、正方形の縁の白マス数はO(1)で数えられるので、O(WH)で全マスをチェックしても間に合う。
なお、仮置きマスと選択マスが同じX座標またはY座標にある場合、両者を通る正方形の大きさは一意に定まらないが、正方形の１辺は２以上なので同じ正方形を構築できるX座標・Y座標ともに異なる仮置きマスが存在するため、そのような仮置きマスは無視してよい。

int H,W,TW;
string S[2011];
int NH[2011][2011],NV[2011][2011];

void draw(int x,int y,int d) {
	int i,yy;
	FOR(i,d) {
		if(S[y][x+i]=='.') S[y][x+i]='+';
		if(S[y+i][x]=='.') S[y+i][x]='+';
		if(S[y+d-1][x+i]=='.') S[y+d-1][x+i]='+';
		if(S[y+i][x+d-1]=='.') S[y+i][x+d-1]='+';
	}
	FOR(yy,H) cout << S[yy] << endl;
}

int numnum(int x,int y,int w) {
	int r=0,i;
	if(x<0 || x+w-1>=W) return 0;
	if(y<0 || y+w-1>=H) return 0;
	
	r+=NH[y][x+w]-NH[y][x];
	r+=NH[y+(w-1)][x+w]-NH[y+(w-1)][x];
	r+=NV[x][y+w]-NV[x][y];
	r+=NV[x+(w-1)][y+w]-NV[x+(w-1)][y];
	r-=(S[y][x]=='w');
	r-=(S[y+(w-1)][x]=='w');
	r-=(S[y][x+(w-1)]=='w');
	r-=(S[y+(w-1)][x+(w-1)]=='w');
	//_P("%d %d %d  %d\n",x,y,w,r);
	return r;
}

void solve() {
	int f,i,j,k,l,x,y,mi=2010,tx,ty,rx,ry,d;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) {
		NV[x][y+1]=NV[x][y];
		NH[y][x+1]=NH[y][x];
		if(S[y][x]=='w') NV[x][y+1]++,NH[y][x+1]++,TW++,tx=x,ty=y;
	}
	if(TW==1) mi=1,rx=tx,ry=ty;
	
	FOR(y,H) FOR(x,W) if(x!=tx&&y!=ty){
		d = max(abs(ty-y),abs(tx-x))+1;
		if(d>mi) continue;
		int x2=(x>tx)?(x-(d-1)):x;
		int y2=(y>ty)?(y-(d-1)):y;
		if(numnum(x2,y2,d)==TW) mi=d,rx=x2,ry=y2;
	}
	
	if(mi!=2010) draw(rx,ry,mi);
	else _P("-1\n");
}

まとめ

最初、「X座標・Y座標がずれた白マスを２点選べば、角が一意に定まる」と勘違いしていた。
２つのマスが対辺にあると角は定まらないのね。