Codeforces Round #281 (Div. 2) D. Vasya and Chess

問題
N*Nのチェス盤があって（座標は1-indexとします）、
(1,1)に自分のクイーン（飛車角両方の動きができるやつ）が、
(1,N)に相手のクイーンがいて、
残りの盤面は全部ポーンがいます。
自分のクイーンをQ、相手のクイーンをq、ポーンをPとすると、

QPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
qPPPPPPP

こんな感じです。

自分が先攻で交互にクイーンを動かしていき、

相手に自分のクイーンを取られる
自分のターンにポーンが取れない

のどちらかになったら負けです。
Nが入力として与えられるので、お互い最善を尽くしたらどちらが勝つのか、自分が勝つ場合は初手でクイーンを動かす座標（複数ある場合は座標が辞書順最小となるもの）も出力しなさい。

制約
2<=N<=10^9

解法
２者の完全情報ゲームというとGrundy数とかが一瞬頭をよぎりますが、Nの制約からしてあまり間に合わなさそうです。
ここで注目すべきは初期状態が線対称な形になっているということです。
この場合、後攻は先攻の動きを真似ることができます。というわけでNが奇数のときは後手必勝です。
Nが偶数のときは、先手のクイーンを１つ下に動かして一番上の行を無視することで、Nが奇数の時の後手のように振る舞うことができます。よってこの場合は先手必勝です（なおかつ、(1,2)という座標は初手で動かせる手の中で辞書順最小です）。

.PPPPPPP
QPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
qPPPPPPP

↑8*8の盤で初手で(1,2)に動いた図。1行目を無視するとNが奇数で相手が先攻と見做せるので先手必勝。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
#include<bitset>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 100000000
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)		idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)	for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)		idp p2((x).F, (x).S)
#define dump(x,n)	idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)	idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)	idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)	idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)	rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)	rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


int main(){
	li n;
	cin>>n;
	if(n%2)puts("black");
	else {
		puts("white");
		puts("1 2");
	}

	return 0;
}

解説を聞いてああなるほど！と思ったわけですが、
「ポーンを取るだけならいいけど、真似た先で相手にとられてしまう場所に来ることはないのか？」
「1行目を自分が無視するのは構わないが、相手が利用することはないと言い切れるのか？」
ということがまだ直感的にピンと来ていない状態です。
おそらく「マネしながらだと上半分から下半分、下半分から上半分に移動できない」ということなのだと思っていますが、ポーンを取ってできた道を使ってもその移動が不可能なのかがまだ怪しいです。。。

追記：
下半分から上半分への移動には、真ん中の行のポーンを最低1つは取らないといけないことになります（奇数行のときを考えているので）。

...P.PP
PP..P.P
PPPQ.PP
PPPPPPP
PPPq.PP
PP..P.P
...P.PP

↑Qが真ん中の行にたどり着きうる局面の例（N=7）。Qが移動できる真ん中の行のマスにはqも必ず移動できる

で、後手側は先手の真似をするだけなのでそれは必ず先手側が行うことになります。
で、後手は先手の真似をしているので、先手がたどり着ける真ん中の行は後手も必ず直後の手でたどり着けます。
よって下半分から上半分への移動は起こりえない、というお話でした。