AtCoder ARC #013 : C - 笑いをとれるかな？

さてCの問題。
いつものCに比べると、実装量は少ないけど知らないと厳しい問題。
http://arc013.contest.atcoder.jp/tasks/arc013_3

問題

いくつかの直方体のサイズが与えられる。
各直方体には、いくつかハバネロが入っており、その座標が与えられる。

２人のプレイヤーは、いずれかの直方体を３軸のうち２軸に平行で、かつ格子点を通る座標で切断し、切断したパーツのどちらかを食べる。
ハバネロを先食べた方が負けである場合、先手プレイヤーが最善を尽くした時に勝てるかどうかを答える。

解答

この問題はNimに持っていくことができる。
各直方体において、ハバネロ群を含む最小の直方体内部は切断できない。
よって、各プレイヤーはハバネロを含む直方体の外側のみ切断することになる。
このとき、プレイヤーは取れるのはハバネロを含む直方体の(X,Y,Z)座標が(大きい,小さい)部分の６か所となるので、これらの座標の大きさでNimを計算すればよい。

int N;
vector<int> nim;

void solve() {
	int f,r,i,j,k,l;
	int x,y,mx,my;
	int B[3];
	int C[3];
	int MI[3],MA[3];
	
	N=GETi();
	FOR(i,N) {
		GET3(&B[0],&B[1],&B[2]);
		MI[0]=MI[1]=MI[2]=1000000001;
		MA[0]=MA[1]=MA[2]=0;
		
		l=GETi();
		FOR(j,l) {
			GET3(&C[0],&C[1],&C[2]);
			FOR(k,3) { MI[k]=min(MI[k],C[k]);MA[k]=max(MA[k],C[k]);}
		}
		FOR(k,3) {
			if(MI[k]>0) nim.push_back(MI[k]-0);
			if(MA[k]<B[k]-1) nim.push_back(B[k]-1-MA[k]);
		}
	}
	
	j=0;
	FOR(i,nim.size()) j ^= nim[i];
	
	_P("%s\n",j?"WIN":"LOSE");
}

まとめ

この問題はさらっとNimに持ちこめて良かった。
なかなか面白い問題。