TopCoder SRM 741 Div2 Hard BoardCoveringDiv2

Div2Hardにしては簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=15145

問題

グリッドが与えられる。
一部のマスは黒く塗られており、残りの白マスはトリオミノで埋められた状態である。
各トリオミノを10色で塗り分け、同色のトリオミノが辺を共有しないようにせよ。

解法

トリオミノの外周長は8なので、端から順に使える色を貪欲に使っていって問題ない。
あとは考察要素はないので以下に簡潔に書くかを工夫しよう。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

vector<pair<int,int>> V[50][50];

class BoardCoveringDiv2 {
	public:
	
	int N;
	vector <string> make(vector <string> B) {
		UF<3000> uf;
		N=B.size();
		int i,y,x;
		
		FOR(y,N) FOR(x,N) {
			V[y][x].clear();
			if(y && B[y][x]==B[y-1][x]) uf(y*N+x,(y-1)*N+x);
			if(x && B[y][x]==B[y][x-1]) uf(y*N+x,y*N+x-1);
		}
		
		FOR(y,N) FOR(x,N) {
			V[uf[y*N+x]/N][uf[y*N+x]%N].push_back({x,y});
		}
		
		FOR(y,N) FOR(x,N) if((B[y][x]<'0' || B[y][x]>'9')&&B[y][x]!='#') {
			vector<pair<int,int>> C=V[uf[y*N+x]/N][uf[y*N+x]%N];
			set<char> S;
			FORR(c,C) {
				int dd[4]={0,1,0,-1};
				FOR(i,4) {
					int ty=c.second+dd[i];
					int tx=c.first+dd[i^1];
					if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
					S.insert(B[ty][tx]);
				}
			}
			char ret='0';
			while(S.count(ret)) ret++;
			FORR(c,C) B[c.second][c.first]=ret;
		}
		return B;
		
	}
}

まとめ

Div1Medium考えてからDiv2の問題に落としたのか、Div2Hardにしては考察要素が少ない。