Codeforces #168 Div2. A. Lights Out、B. Convex Shape

さて#168。今回はDiv1で出てA,Bを解き、ちょっとHackしたらそこそこの順位になった。
ではDiv1Cまで練習。まずはDiv2問題から。
http://codeforces.com/contest/275/problem/A
http://codeforces.com/contest/275/problem/B

A. Lights Out

3x3の領域でライツアウトを行う。
初期状態ではすべてのマスの明かりはついている。
各マスのスイッチを押すと、そのマスと隣接マスの明かりのオンオフが切り替わる。
各マスでスイッチを押した回数が与えられたとき、最終的な明かりのオンオフを答える。

スイッチを２回押すと元に戻るので、結局各マススイッチを押した回数が奇数なら１回だけスイッチを押したとみなしてシミュレートすればよい。

int mat[5][5];

void solve() {
	int f,r,i,j,k,l, x,y,loop;
	ll LH,CL,hoge;
	
	for(y=1;y<=3;y++) for(x=1;x<=3;x++) {
		if(GETi()%2) {
			mat[y][x]^=1;
			mat[y][x-1]^=1;
			mat[y][x+1]^=1;
			mat[y-1][x]^=1;
			mat[y+1][x]^=1;
		}
		
	}

	FOR(y,3) _P("%d%d%d\n",1-mat[y+1][1],1-mat[y+1][2],1-mat[y+1][3]);
	return;
}

B. Convex Shape

マス目状の各マスが白黒で塗られている。
黒い部分が凸かどうかを返す。
なお、凸の定義は、任意の２つのマスをつなぐとき、最大１回だけ曲がってたどり着けることである。

各マスから、１回だけ曲がって他のマスにたどり着けるか試す。
まず１回も曲がらずに各マスから上下左右に黒マスが連続してるマスに移動できる。
さらに、１回も曲がらず辿りつけるマスから、さらに上下左右に連続する黒マスには１回曲がるだけで到達できる。

この手法はO(N^4)程度かかるが、Nが高々50なので問題ない。

int H,W;
char mat[60][60];

int okok() {
	int y,x,y2,x2,tx,ty,l;
	int vis[60][60];
	int dx[4]={0,0,1,-1};
	int dy[4]={1,-1,0,0};
	
	FOR(y,H) FOR(x,W) {
		if(mat[y][x]=='W') continue;
		
		MINUS(vis);
		vis[y][x]=0;
		
		FOR(l,4) {
			tx=x;ty=y;
			while(1) {
				tx+=dx[l];
				ty+=dy[l];
				if(tx<0 || tx>=W || ty<0 || ty>=H) break;
				if(mat[ty][tx]=='W') break;
				vis[ty][tx]=1;
			}
		}
		FOR(y2,H) FOR(x2,W) {
			if(vis[y2][x2] != 1) continue;
			FOR(l,4) {
				tx=x2;ty=y2;
				while(1) {
					tx+=dx[l];
					ty+=dy[l];
					if(tx<0 || tx>=W || ty<0 || ty>=H) break;
					if(mat[ty][tx]=='W') break;
					if(vis[ty][tx]==-1) vis[ty][tx]=2;
				}
			}
		}
		FOR(y2,H) FOR(x2,W) {
			if(mat[y2][x2]=='B' && vis[y2][x2]==-1) return 0;
		}
	}
	
	return 1;
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	GET2(&H,&W);
	FOR(y,H) GETs(mat[y]);
	
	_P("%s\n",(okok()?"YES":"NO"));
	return;
}

まとめ

Bの問題は適当に書いたとはいえちょっと長いな。
もっとうまく書けそう。