TopCoder SRM 788 : Div1 Medium SoccerStadium

Resubmitとかいろいろ反省点が大きい。
https://community.topcoder.com/stat?c=problem_statement&pm=16055&rd=18085

問題

H*Wのグリッドが与えられる。
隣接セルの境界は、一部壁で区切られている。
ここから任意に壁を取り除き、 グリッドが壁によっていくつかの矩形に分けられかつ矩形内に壁のない状態を作りたい。
最大何個の矩形からなる状態を構築できるか。

解法

間に壁がないセルを連結していこう。
連結成分のうち、「矩形かつ壁がない」という状態でないものに対して、その連結成分の左端・右端・上端・下端で囲まれた領域内の壁を取っ払い連結させる、ということを繰り返していくとよい。
セル数はさほど多くないので、ループ回数は割と雑で行ける。

なお、自分は「矩形かつ壁がない」の判定は連結成分の左端・右端・上端・下端・セル数を保持しながらUnion-Findすることで行ったが、セル数が少ないので逐一BFSとかしても多分間に合う。

int L[505],R[505];
int U[505],D[505];
int A[505];


template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1010> uf;

class SoccerStadium {
	public:
	
	void merge(int a,int b) {
		a=uf[a];
		b=uf[b];
		if(a!=b) {
			L[a]=L[b]=min(L[a],L[b]);
			R[a]=R[b]=max(R[a],R[b]);
			U[a]=U[b]=min(U[a],U[b]);
			D[a]=D[b]=max(D[a],D[b]);
			A[a]=A[b]=A[a]+A[b];
			uf(a,b);
		}
	}
	
	int maximumGames(int H, int W, vector <string> S) {
		uf.reinit();
		
		int y,x;
		FOR(y,H) FOR(x,W) L[y*W+x]=R[y*W+x]=x, U[y*W+x]=D[y*W+x]=y, A[y*W+x]=1;
		FOR(y,H) FOR(x,W) {
			if(x<W-1&&S[2*y+1][2*x+2]!='|') merge(y*W+x,y*W+x+1);
			if(y<H-1&&S[2*y+2][2*x+1]!='-') merge((y+1)*W+x,y*W+x);
		}
		
		int i,j;
		FOR(i,500) {
			FOR(j,H*W) if(uf[j]==j) {
				int ta=(R[j]-L[j]+1)*(D[j]-U[j]+1);
				if(ta!=A[j]) {
					for(y=U[j];y<=D[j];y++) {
						for(x=L[j];x<=R[j];x++) {
							if(x<R[j]) merge(y*W+x,y*W+x+1);
							if(y<D[j]) merge((y+1)*W+x,y*W+x);
						}
					}
				}
			}
		}
		
		int ret=0;
		FOR(j,H*W) if(uf[j]==j) ret++;
		return ret;
		
		
	}
}

まとめ

BitDP解を検討して時間を食ったり、1ChalミスしたりResubmitしたりグダグダ。