kmjp's blog

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

AtCoder ARC #012 : C - 五目並べチェッカー

さて問題C。
練習の際、解法はすぐわかったけどWAを2回してしまった。
これでは本番参加しててもそこそこの順位にしかなんなかったな。
http://arc012.contest.atcoder.jp/tasks/arc012_3

問題

五目並べの盤面が与えられる。
この盤面が、普通に五目並べを行っていて到達可能かどうか回答する。

解法

到達可能である条件は以下の通り。

  • 黒石と白石の数は、一致しているか黒石が1つ多くなければらない。そうでなければ到達不可。
  • 最後に石を打った番の方は、1つ石を取り除くと5石連続しない(そうしないと途中で対戦が終了しているから)
  • 最後に石を打った番でない方は、5石連続しない。

黒石と白石の数が同じなら最後の1手は白、黒石が1つ大きければ最後は黒。
それを意識して5石連続の有無を探せばよい。
「1つ石を取り除くと5石連続しない」は盤面のサイズNに対し適当にやってもO(N^4)なのでN<=19なら計算量は問題なし。

int W=19,H=19;
char B[20][20];
int no,nx;

int goal(char c) {
	int x,y;
	
	FOR(y,19) FOR(x,19) {
		if(B[y][x]!=c) continue;
		
		if(x<15 && B[y][x+1]==c && B[y][x+2]==c && B[y][x+3]==c && B[y][x+4]==c) return 1;
		if(y<15 && B[y+1][x]==c && B[y+2][x]==c && B[y+3][x]==c && B[y+4][x]==c) return 1;
		if(x<15 && y<15 && B[y+1][x+1]==c && B[y+2][x+2]==c && B[y+3][x+3]==c && B[y+4][x+4]==c) return 1;
		if(x>=4 && y<15 && B[y+1][x-1]==c && B[y+2][x-2]==c && B[y+3][x-3]==c && B[y+4][x-4]==c) return 1;
	}
	
	return 0;
	
}

void solve() {
	int f,r,i,j,k,l;
	int x,y,mx,my;
	
	no=nx=0;
	FOR(y,19) {
		GETs(B[y]);
		FOR(x,19) {
			if(B[y][x]=='o') no++;
			if(B[y][x]=='x') nx++;
		}
	}
	
	if(no!=nx && no!=nx+1) {
		_P("NO\n");
		return;
	}
	
	char c1 = (no==nx)?'o':'x';
	char c2 = (no==nx)?'x':'o';
	
	if(goal(c1)) {
		_P("NO\n");
		return;
	}
	
	int ng=0;
	FOR(y,19) FOR(x,19) {
		if(B[y][x]==c2) {
			B[y][x]='.';
			if(!goal(c2)) {
				_P("YES\n");
				return;
			}
			ng++;
			B[y][x]=c2;
		}
	}
	
	if(ng) _P("NO\n");
	else _P("YES\n");
	
	return;
}

まとめ

面倒なので5石並びの判定はif文をだらだら並べてやってしまった。
解法がさっと思いつけたので良かった。