Codeforces #170 Div1. C. Game

本番中はBで手こずって解けなかったけど、後で落ち着いて解いたらノーヒントで解けた問題。
ただ、20回位WAしての結果だけど…。
http://codeforces.com/contest/277/problem/C

問題

縦横の長さがW,H(<=10^9)の長方形の紙がある。
ここに縦または横方向に沿ってK個の切れ目がある。
これらの切れ目は重複する領域があることもある。

この状態でゲームを開始する。
２人が交互に紙を切る。この際、今まで切ってない場所を最低長さ1以上切らなければいけない。
すでに切った場所をもう１回切っても良い(新規に切る場所を長さ1分含んでいれば)。
紙がすべて1x1に裁断され、これ以上きれなくなったら負け。

２人が最適手を取るときの勝者を答えよ。
また、先手が勝つ場合は１手目の切り方を答えよ。

解法

典型的なNimである。
切る余地があるのは、(H-1)個の長さWの横方向のラインと、(W-1)個の長さHの縦方向のライン。
ここから、すでにある切れ目の長さを引いてNimを計算すればよい。

ちょっと面倒なのが、複数の切れ目が同じ場所を複数回切る場合があること。
そのため、各ラインにおいて切れ目を整理するsimplify関数を作って処理した。

また、ラインの数が最大10^9本のオーダーであるけど、切れ目がないラインについてはすべて長さが同じなので、ラインの数だけNim計算のxorを取る必要はなく、ライン数が奇数だったら１回だけ長さのxorを取ればよい。

Nimが0の時は後手が勝ち、0以外の時は先手が勝つ。
先手が勝つ場合は、もっとも長さが長いラインからNim分だけ引けばよい。
すでに切れ目があるラインからさらにNim分引くのはちょっと面倒。

int W,H,K,NX,NY;
map<int, vector<pair<int,int> > > MX,MY;
map<int, vector<int> > MSX,MSY;
map<int, int > WX,WY;


void simplify(map<int, vector<pair<int,int> > >::iterator mit, int isx) {
	sort(mit->second.begin(),mit->second.end());
	vector<int> si;
	int i;
	int spos=0;
	int stat=0;
	int w=0;
	int maw = isx?W:H;
	
	FOR(i,mit->second.size()) {
		
		if(mit->second[i].second==0) {
			if(stat==0) {
				si.push_back(mit->second[i].first);
				w+=mit->second[i].first - spos;
			}
			stat++;
		}
		else {
			if(stat==1) {
				si.push_back(mit->second[i].first);
				spos=mit->second[i].first;
			}
			stat--;
		}
	}
	
	w+=maw-spos;
	
	if(isx) {
		MSX[mit->first] = si;
		WX[mit->first] = w;
	}
	else {
		MSY[mit->first] = si;
		WY[mit->first] = w;
	}
	
}

int output(vector<int> V, int nim) {
	int pos=0;
	int i=0;
	
	while(1) {
		if(i>=V.size() || pos+nim <= V[i]) return pos+nim;
		nim -= V[i]-pos;
		pos=V[i+1];
		i+=2;
	}
}

void solve() {
	int f,r,i,j,k,l,x,y,x1,x2,y1,y2,w;
	ll t;
	
	W=GETi();
	H=GETi();
	K=GETi();
	FOR(i,K) {
		x1=GETi();
		y1=GETi();
		x2=GETi();
		y2=GETi();
		if(y1==y2) {
			//yoko
			MX[y1].push_back(make_pair(min(x1,x2),0));
			MX[y1].push_back(make_pair(max(x1,x2),1));
		}
		else {
			//tate
			MY[x1].push_back(make_pair(min(y1,y2),0));
			MY[x1].push_back(make_pair(max(y1,y2),1));
		}
	}
	
	NX=H-1-MX.size();
	NY=W-1-MY.size();
	map<int, vector<pair<int,int> > >::iterator mit;
	for(mit=MX.begin();mit!=MX.end();mit++) simplify(mit,1);
	for(mit=MY.begin();mit!=MY.end();mit++) simplify(mit,0);
	
	int nim=0;
	if(NX&1) nim ^= W;
	if(NY&1) nim ^= H;
	
	map<int, int>::iterator mit2;
	for(mit2=WX.begin();mit2!=WX.end();mit2++) nim ^= mit2->second;
	for(mit2=WY.begin();mit2!=WY.end();mit2++) nim ^= mit2->second;
	
	if(nim==0) {
		_P("SECOND\n");
	}
	else {
		_P("FIRST\n",nim);
		
		for(i=1;i<min(H,100003);i++) {
			if(MSX.find(i)==MSX.end()) {
				if((nim^W)<=W) {
					_P("%d %d %d %d\n",0,i,W-(nim^W),i);
					return;
				}
			}
			else {
				if((nim ^ WX[i]) > WX[i]) continue;
				_P("%d %d %d %d\n",0,i,output(MSX[i],WX[i]-(nim^WX[i])),i);
				return;
			}
		}
		for(i=1;i<min(W,100003);i++) {
			if(MSY.find(i)==MSY.end()) {
				if((nim^H)<=H) {
					_P("%d %d %d %d\n",i,0,i,H-(nim^H));
					return;
				}
			}
			else {
				if((nim^WY[i])>WY[i]) continue;
				_P("%d %d %d %d\n",i,0,i,output(MSY[i],WY[i]-(nim^WY[i])));
				return;
			}
		}
		
	}
	
	return;
}

まとめ

単なるNimなら楽なんだけど、先手の最適手を答えるためのデータ構造が面倒。
おかげでみんな割とコードが長め。
でもそれも踏まえて解き切れて良かった。