Codeforces #532 Div2 D. Dasha and Chess

この回は遅れて参加したので全完はできず。
https://codeforces.com/contest/1100/problem/D

問題

999x999の盤面上にチェスの駒を置く。
初期状態で１個のキングと666個のルークがある。
先手であるプレイヤーはキングを動かし、ルークの射程範囲内に入れれば勝ちである。
後手は、ルークを１つ選び(本来のチェスのルールとは異なり)任意の位置に移動できる。
それにより、ルークの射程範囲にキングを入れないようにする。

先手の必勝例を答えよ。

解法

まずキングを中心に移動させよう。
すると、４つの象限のうちルークの総数が最小でない３つの和は必ず500以上になる。
そしたらその３つの象限のうち真ん中の証言について、斜めに角まで移動しよう。
角まで移動するには499手かかるが、その間500個以上のルークを移動させないといけないので後手必敗となる。

int X,Y;
int RX[667],RY[667];
int Ys[1010],Xs[1010];

void check() {
	if(Xs[X-1]) {
		cout<<X-1<<" "<<Y<<endl;
		exit(0);
	}
	if(Xs[X+1]) {
		cout<<X+1<<" "<<Y<<endl;
		exit(0);
	}
	if(Ys[Y-1]) {
		cout<<X<<" "<<Y-1<<endl;
		exit(0);
	}
	if(Ys[Y+1]) {
		cout<<X<<" "<<Y+1<<endl;
		exit(0);
	}
}

void check2() {
	int i,x,y;
	cin>>i>>x>>y;
	if(i==-1) exit(0);
	i--;
	Xs[RX[i]]--;
	Ys[RY[i]]--;
	RX[i]=x;
	RY[i]=y;
	Xs[RX[i]]++;
	Ys[RY[i]]++;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	FOR(i,666) {
		cin>>RX[i]>>RY[i];
		Xs[RX[i]]++;
		Ys[RY[i]]++;
	}
	while(X!=500 || Y!=500) {
		int dx=0,dy=0;
		
		check();
		if(X>500) dx=-1;
		if(X<500) dx=1;
		if(Y>500) dy=-1;
		if(Y<500) dy=1;
		X+=dx;
		Y+=dy;
		cout<<X<<" "<<Y<<endl;
		check2();
	}
	
	int C[2][2]={};
	FOR(i,666) C[RX[i]>500][RY[i]>500]++;
	int dx,dy;
	if(C[0][0]<=666-499) dx=dy=1;
	if(C[0][1]<=666-499) dx=1, dy=-1;
	if(C[1][0]<=666-499) dx=-1, dy=1;
	if(C[1][1]<=666-499) dx=dy=-1;
	
	while(1) {
		check();
		X+=dx;
		Y+=dy;
		cout<<X<<" "<<Y<<endl;
		check2();
	}
	
}

まとめ

プログラムというよりパズルを解いている感覚だな…。