Codeforces #180 Div1 D. Color the Carpet

実装は単純だけどひらめきは面白い問題。
http://codeforces.com/contest/297/problem/D

問題

HxWのグリッドの各セルをK色で塗り分けたい。
ここで、各隣接マスについて、色が一致すべきか異なるべきかの条件が与えられる。
条件を75%以上満たす色の塗り方を答えよ。

解法

端から斜めに塗りつぶせばいいかなーとか思ったけど、結局Editorialを見て回答。

K==1の時は塗り方は一通りなので、それが条件を75%満たすが判定するだけ。

K>=2の時は、実は２色で条件を満たすことができる。
まず前提としてW>Hとする。（これを満たさない場合は縦横逆で処理する）

まず各行、左端を適当に色を決めて、後は横方向の条件を満たすよう左端から２色の色を定めていく。
次に上から順にi行目と(i-1)行目の間の条件一致不一致を判定し、半分以上条件に合わないなら、i行目の色をすべて反転する。

上記のようにすると、横方向の条件H*(W-1)個は条件を満たす。
さらに縦方向の条件(H-1)*Wは半分以上条件を満たすので、H*(W-1)+(H-1)*W/2=(2HW-H-W+(W-H)/3)*(3/4)>=(2HW-H-W)*(3/4)を満たす。

int H,W,K;
char LR[1001][1001];
char UD[1001][1001];
int res[1001][1001];

void solve() {
	int i,j,k,l,r,x,y,sw=0; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		FOR(x,W-1) cin>>LR[y][x], LR[y][x]=LR[y][x]=='N';
		if(y<H-1) FOR(x,W) cin>>UD[y][x], UD[y][x]=UD[y][x]=='N';
	}
	
	if(K==1) {
		int ret=0;
		FOR(y,H) FOR(x,W-1) ret+=LR[y][x];
		FOR(y,H-1) FOR(x,W) ret+=UD[y][x];
		if(ret*4>H*(W-1)+(H-1)*W) return _P("NO\n");
		_P("YES\n");
		FOR(y,H) FOR(x,W) _P("1%s",x==W-1?"\n":" ");
		return;
	}
	
	
	if(W<H) {
		FOR(x,W) {
			for(y=1;y<H;y++) res[y][x]=res[y-1][x]^UD[y-1][x];
			if(x>0) {
				int wo=0;
				FOR(y,H) wo+=res[y][x]^res[y][x-1]^LR[y][x-1];
				if(wo>H/2) FOR(y,H) res[y][x]^=1;
			}
		}
	}
	else {
		FOR(y,H) {
			for(x=1;x<W;x++) res[y][x]=res[y][x-1]^LR[y][x-1];
			if(y>0) {
				int wo=0;
				FOR(x,W) wo+=res[y][x]^res[y-1][x]^UD[y-1][x];
				if(wo>W/2) FOR(x,W) res[y][x]^=1;
			}
		}
	}
	_P("YES\n");
	FOR(y,H) FOR(x,W) _P("%d%s",res[y][x]+1,x==W-1?"\n":" ");
}

まとめ

発想が面白い問題でした。
CodeforcesはあまりSRMにない、こういう遊び心の多い問題があるのがいいな。