kmjp's blog

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

Google Code Jam 2015 Qualification Round : D. Ominous Omino

なかなか面白い問題。
https://code.google.com/codejam/contest/6224486/dashboard#s=p3

問題

X-ポリオミノを幾つか使い、R*Cの二次元グリッドを埋めるゲームを考える。

先手は、X-ポリオミノを1つ指定する。
後手は任意のX-ポリオミノを使いR*Cの二次元グリッドを埋める。
ただし、後手は先手の指定したX-ポリオミノを最低1回使わなければならない。
なお、X-ポリオミノは回転や反転しても良い。

後手がどうやってもグリッドを埋められない場合、先手の勝ちである。
先手がどのX-ポリオミノを用いても後手がR*Cグリッドを埋められる場合、後手の勝ちである。
X,R,Cが与えられたとき、先手・後手のどちらが勝つか答えよ。

解法

問題文中にヒントがある。
7-ポリオミノは中空のある形状がある。
よって、X=7以上では、先手が同様に中空のある形状を指定すれば後手はグリッドを埋められず先手の勝ちである。

よって以後X≦6の事だけ考えればよい。
これは地道に総当たりすればよい。
まず最初にX-ポリオミノをX≦6の範囲で全列挙しておく。
ヘキソミノでもパターンは216個しかないので計算量は問題ない。

先手が各X-ポリオミノを指定した場合、後手がそれをどこに置いても残りを埋められないケースがある場合、先手の勝ちとなる。

これにはUnion-Findを用いて判定できる。
まず先手の指定したX-ポリオミノをどこかに置いた場合、残りの領域について隣接セル同士をUnion-Findで連結する。
各連結成分がXの倍数なら残りはX-ポリオミノで埋められ、そうでないなら埋められない。

(注:一般に、Xの倍数個の連結マスがX-ポリオミノで埋められるとは限らない。例えば以下の状況を
ドミノ2個で埋めることはできない。ただし恐らくヘキソミノ以下のX-ポリオミノ1個置いてそのような状況は作れないので、本問においてはこれで良いと考えられる。現在調査中。)

**.
*..
**.

後手は先手の指定したX-ポリオミノを回転できることに注意。
以下のコードでは、ポリオミノの回転が面倒なのでR*Cのグリッド側を回転して判定している。

set<ll> S[7];
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

bool fail(ll mask,int H,int W,int X) {
	int h=0,w=0,y,x,ty,tx;
	int did[25][25];
	while(mask&(255LL<<(h*8))) h++;
	while(mask&((0x0101010101010101LL)<<w)) w++;
	
	for(y=0;y+h-1<H;y++) for(x=0;x+w-1<W;x++) {
		ZERO(did);
		UF<900> uf;
		FOR(ty,h) FOR(tx,w) if(mask & (1LL<<(ty*8+tx))) did[y+ty][x+tx]=1;
		FOR(ty,H) FOR(tx,W) {
			if(ty<H-1 && did[ty][tx]==did[ty+1][tx]) uf(ty*W+tx,(ty+1)*W+tx);
			if(tx<W-1 && did[ty][tx]==did[ty][tx+1]) uf(ty*W+tx,ty*W+tx+1);
		}
		int ok=1;
		FOR(ty,H) FOR(tx,W) if(uf.count(ty*W+tx)%X) ok=0;
		if(ok) return false;
	}
	return true;
}

bool win(int X,int R,int C) {
	if(X>=7) return true;
	if(X>max(R,C)) return true;
	if(R*C%X) return true;
	if(min(R,C)>=X+2) return false;
	
	ITR(it,S[X]) {
		if(fail(*it,R,C,X) && fail(*it,C,R,X)) return true;
	}
	return false;
	
}

void solve(int _loop) {
	int X,R,C;
	cin>>X>>R>>C;
	
	if(win(X,R,C)) _P("Case #%d: RICHARD\n",_loop);
	else _P("Case #%d: GABRIEL\n",_loop);
}

まとめ

ややこしいけど、時間のある予選向きの問題。