Codeforces #249 Div2 E. Special Graph

これは知らないと無理なような…。
http://codeforces.com/contest/435/problem/E

問題

先のD問題同様に線で接続されたNxM個の点がある。
これらの点のうち一部は４色のいずれかで塗られており、残りは塗られていない。

線で接続された点が互いに同じ色にならないように、塗られていない点の塗り方を答えよ。

解法

以下のDiv1 Hardに似た問題があり、そのEditorialが参考になる。
SRM 472 Editorial

実は色の塗り分け方のパターンはかなり限られる。
例えば左上2x2を以下のように塗ったとする。

AB
CD

この時、題意を満たす塗り分け方は以下のいずれかである。

• ２行ごとに同じパターンを繰り返す。奇数行目はABABAB..かBABABA..、偶数行目はCDCDCD...かDCDCDC...。
• ２列ごとに同じパターンを繰り返す。奇数列目はACACAC..かCACACA..、偶数行目はBDBDBD...かDBDBDB...。

よって、左上4点の色を4!通り総当たりし、両パターンのいずれかですでに塗られた点と色が矛盾しないものを答えればよい。

int H,W;
char S[1001][1001];
char S2[1001][1001];

void dor() { // same 2 row
	int y,x,j;
	
	FOR(y,2) {
		FOR(x,W) if(S[y][x]!=S2[y][x%2]&&S[y][x]!='0') return;
		FOR(x,W) S2[y][x]=S2[y][x%2];
	}
	for(y=2;y<H;y++) {
		int ng=0;
		FOR(x,W) if(S[y][x]!='0') {
			if(S[y][x]!=S2[y%2][x%2]) ng|=1;
			if(S[y][x]!=S2[y%2][(x%2)^1]) ng|=2;
		}
		if(ng==3) return;
		j=(ng==1);
		FOR(x,W) S2[y][x]=S2[y%2][(x%2)^j];
	}
	FOR(y,H) _P("%s\n",S2[y]);
	exit(0);
}

void doc() { // same 2 col
	int y,x,j;
	
	FOR(x,2) {
		FOR(y,H) if(S[y][x]!=S2[y%2][x]&&S[y][x]!='0') return;
		FOR(y,H) S2[y][x]=S2[y%2][x];
	}
	for(x=2;x<W;x++) {
		int ng=0;
		FOR(y,H) if(S[y][x]!='0') {
			if(S[y][x]!=S2[y%2][x%2]) ng|=1;
			if(S[y][x]!=S2[(y%2)^1][x%2]) ng|=2;
		}
		if(ng==3) return;
		j=(ng==1);
		FOR(y,H) S2[y][x]=S2[(y%2)^j][x%2];
	}
	FOR(y,H) _P("%s\n",S2[y]);
	exit(0);
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	char C[5]="1234";
	
	do {
		S2[0][0]=C[0];
		S2[0][1]=C[1];
		S2[1][0]=C[2];
		S2[1][1]=C[3];
		dor();
		doc();
	} while(next_permutation(C,C+4));
	
	_P("0\n");
}

まとめ

パターンを知らないと無理だよなぁ…。