kmjp's blog

競技プログラミング参加記です

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

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

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

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

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

この手法は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の問題は適当に書いたとはいえちょっと長いな。
もっとうまく書けそう。

広告を非表示にする