Google Code Jam 2013 Qualification Round : A. Tic-Tac-Toe-Tomek、B. Lawnmower

今年もGCJに参加。今回は予選から手ごたえのある問題で、本番にD-Largeは解けず…。
C-Large2を解けたのは手ごたえがあって良かった。
では復習。
https://code.google.com/codejam/contest/2270488/dashboard#s=p0
https://code.google.com/codejam/contest/2270488/dashboard#s=p1

A. Tic-Tac-Toe-Tomek

4目並べの勝者を答える問題。
通常の４目並べの"X""O"に加え、両者にとって自分のコマとしてカウントできる"T"という記号がある。

縦４通り、横４通り、斜め２通りの計10通りを地道に調べるだけ。
Largeでもマスの数は変わらないし、時間は問題ない。

char line[5][5];
int wx,wo;

void chk(char a,char b,char c,char d) {
	int cnt[256];
	ZERO(cnt);
	cnt[a]++;
	cnt[b]++;
	cnt[c]++;
	cnt[d]++;
	
	if(cnt['X']==4 || (cnt['X']==3 && cnt['T']==1)) wx=1;
	if(cnt['O']==4 || (cnt['O']==3 && cnt['T']==1)) wo=1;

}

void solve(int _loop) {
	int i,j,x,y,ne=0;
	
	FOR(y,4) {
		while(1) {
			GETs(line[y]);
			if(strlen(line[y])>=4) break;
		}
		FOR(x,4) if(line[y][x]=='.') ne=1;
	}
	wx=wo=0;
	chk(line[0][0],line[0][1],line[0][2],line[0][3]);
	chk(line[1][0],line[1][1],line[1][2],line[1][3]);
	chk(line[2][0],line[2][1],line[2][2],line[2][3]);
	chk(line[3][0],line[3][1],line[3][2],line[3][3]);
	chk(line[0][0],line[1][0],line[2][0],line[3][0]);
	chk(line[0][1],line[1][1],line[2][1],line[3][1]);
	chk(line[0][2],line[1][2],line[2][2],line[3][2]);
	chk(line[0][3],line[1][3],line[2][3],line[3][3]);
	chk(line[0][0],line[1][1],line[2][2],line[3][3]);
	chk(line[0][3],line[1][2],line[2][1],line[3][0]);
	
	if(wx) {
		_PE("Case #%d: X won\n",_loop);
	}
	else if(wo) {
		_PE("Case #%d: O won\n",_loop);
	}
	else {
		if(ne) {
			_PE("Case #%d: Game has not completed\n",_loop);
		}
		else {
			_PE("Case #%d: Draw\n",_loop);
		}
	}
}

B. Lawnmower

グリッド状に構成された芝生に対し、芝刈り機を芝を刈っていく。
芝刈り機をある高さHに設定し、横１行または縦１列の芝を刈ると、芝の高さがH以上のマスはHになる。
ここで芝の高さのパターンが与えられたとき、芝刈り機でその芝を再現できるかを答える。

各行・各列の最高の高さを求めると、その行・列で動かせる最低の高さの芝刈り機の設定がわかる。
そして各マスの高さが、行または列の芝刈り設定の低い方に一致するか判定すればよい。

int H,W;
int hei[300][300];
int HX[300],HY[300];

void solve(int _loop) {
	int i,j,x,y;
	
	GET2(&H,&W);
	ZERO(HX);
	ZERO(HY);
	FOR(y,H) FOR(x,W) {
		hei[y][x]=GETi();
		HX[y] = max(HX[y],hei[y][x]);
		HY[x] = max(HY[x],hei[y][x]);
	}
	int ng=0;
	FOR(y,H) FOR(x,W) if(hei[y][x]!=min(HX[y],HY[x])) ng=1;
	
	_PE("Case #%d: %s\n",_loop,ng?"NO":"YES");
}

まとめ

Bはちょっと考えさせられた問題で面白かった。
最初、芝刈り機は１列または１行走り抜けるのではなく、途中まで行って戻るのもありかなと問題文を勘違いした。
これはこれで問題として面白そう。