Codeforces #246 Div2 E. Square Tiling

いかにもCodeforcesっぽい楽しい問題。
http://codeforces.com/contest/432/problem/E

問題

NxMの２次元グリッドを以下のように色で塗り分けよ。

1. 色はA～Zの文字で表すとする。
2. 各セルの色を文字列として表したとき、辞書順最小である。
3. 同色の隣接マス群は正方形を成す。

解法

左上から順に、色が未確定なマスに出会うたびに色を塗っていく。
まず、上記条件3より、すでに正方形に塗られたマスと同じ色を隣接させるわけにはいかないので、塗る色は上と左と異なる辞書順最小の色である。

次にこの色を何x何の大きさの正方形に塗るかが問題である。

• 塗る色がAなら、これはできるだけ多く塗りたいので、他の確定済みマスにぶつからない限り大きな正方形に塗る。
• 塗る色がBなら、途中でAに切り替えられるならそこからはAを塗りたいがそうでない限りはBを大きく塗りたい。
  • Bで塗る正方形を大きくする場合、途中でAに切り替えられる条件は上にAが来ない場合である。逆に上にAが来る限り、大きな正方形を塗る。
• 塗る色がC以降なら、１マス塗って終わりにする。なぜならその右マスによって、左マスがC以上のため、上が何であれAかBが塗れるからである。

int N,M;
char mat[106][106];

void dodo(int Y,int X) {
	char c='A';
	while((Y>0&&c==mat[Y-1][X]) || (X>0&&c==mat[Y][X-1]) || (Y<N-1&&c==mat[Y+1][X]) || (X<M-1&&c==mat[Y][X+1])) c++;
	
	int sz,x,y;
	for(sz=2;sz<=100;sz++) {
		if(Y+sz>N || X+sz>M) break;
		FOR(x,sz) if(mat[Y+sz-1][X+x]!='$') goto out;
		FOR(y,sz) if(mat[Y+y][X+sz-1]!='$') goto out;
		if(c=='A' && Y>=1 && mat[Y-1][X+sz-1]=='A') goto out;
		if(c=='B' && (Y==0 || mat[Y-1][X+sz-1]!='A')) goto out;
		if(c=='C') goto out;
	}
	out:
	sz--;
	FOR(y,sz) FOR(x,sz) mat[Y+y][X+x]=c;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	ZERO(mat);
	FOR(y,N) FOR(x,M) mat[y][x]='$';
	FOR(y,N) FOR(x,M) if(mat[y][x]=='$') dodo(y,x);
	
	FOR(y,N) cout << mat[y] << endl;
	
}

解法

本番に正答まで行かなかったのは惜しいけど、こういう問題は好きだな。