kmjp's blog

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

Codeforces #281 Div2 D. Vasya and Chess

これは割とすんなり。
http://codeforces.com/contest/493/problem/D

問題

N*Nのグリッドがある。
初期状態で、先手の白いクイーンは(1,1)、後手の黒いクイーンは(1,N)におり、他のセルはすべて緑の駒で埋まっている。

ここで両者交互にクイーンを動かす。
クイーンはチェスのように8方向に移動できるが、その際、いずれか他の駒のいる場所に止まらなければならない。
その際、その駒は取り除く。
移動の時は他の駒を飛び越すことはできない。

相手のクイーンを先に取り除いた方が勝者である。
両者が最適手を取ったとき、勝者はどちらか。
また、先手が勝者なら1手目を答えよ。

解法

Nが奇数なら後手、偶数なら先手必勝である。
奇数の場合、後手は先手と線対称の位置に移動すると、先手が先に中央の列に入らざるを得ないので、後手はそこに重なるように移動すると勝利できる。

Nが偶数の場合、先手が(1,2)に移動すれば、後は上記と逆の状態に持ち込めるので先手が勝つ。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%2) return _P("black\n");
	_P("white\n1 2\n");
}

まとめ

面白い気づきの問題。