Codeforces #468 Div1 D. Game with Tokens

本番かなり怖かったけど通ってよかった。
http://codeforces.com/contest/930/problem/D

問題

グリッド上に1つの白石と複数の黒石があるとする。
黒石の数と位置はすでに定められている。

ここで以下のようなゲームを行う。２人交互にターン制で石を動かす。

• 先手は白い石を必ず隣接マスに動かす。動かしたあと黒石に重なると負ける。
• 後手は黒い石をそれぞれ同時に隣接マスに動かす。各石の動かし方は異なってもよく、移動後重なってもよい。黒石の移動で白い石と重なっても先手は負けとならない。

白い石の初期位置のうち、後手必勝となる位置はいくつか。

解法

最後白が動いて負けということは、負ける直前白石は四方を黒石で囲まれなければならない。
さらにその状態を巻き戻して考えると、先手のターンの直前、白石の四方を囲うような構成に到達できるならば後手の勝ちである。

白石の左右上下に隣接した状態で先手のターンを回すには、白石の上方(厳密には列の差より行の差の方が大きい場合)、下方、左方、右方にそれぞれ位置のパリティが異なる石が1個ずつあればよい。
逆に考えると、黒石がある場合、黒石の下方に白石がある場合は、(パリティされ条件を満たせば)いずれ白石の上をふさぐように移動できることになる。
よって、各黒石について上下左右のカバー範囲をそれぞれ求めよう。
マスのうち上下左右いずれもカバーされるマスがあれば、そこは先手が負ける位置である。

以下のコードでは前処理として各X座標について、上下方向にカバーされる上端下端を求めておき、次にY座標を平面走査しつつ左右方向にカバーされる左端右端を求め、その範囲で上下方向にカバーされる領域をBITで数え上げていく。
BITはパリティを考慮してX,Y座標の偶奇に応じ４面持っている。

int N;
int U[2][205020];
int D[2][205020];
int L[2][205020];
int R[2][205020];
int X[101010],Y[101010];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt[2][2];

vector<int> add[202020];
vector<int> del[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,202200) {
		D[0][i]=D[1][i]=20202000;
		U[0][i]=U[1][i]=-20202000;
		R[0][i]=R[1][i]=20202000;
		L[0][i]=L[1][i]=-20202000;
	}
		
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]+=101000;
		Y[i]+=101000;
		j=(X[i]+Y[i])%2;
		D[j][X[i]]=min(D[j][X[i]],Y[i]+1);
		U[j][X[i]]=max(U[j][X[i]],Y[i]-1);
		R[j][Y[i]]=min(R[j][Y[i]],X[i]+1);
		L[j][Y[i]]=max(L[j][Y[i]],X[i]-1);
	}
	FOR(j,2) {
		FOR(i,202000) {
			U[j][i+1]=max(U[j][i+1],U[j][i]-1);
			D[j][i+1]=min(D[j][i+1],D[j][i]+1);
			L[j][i+1]=max(L[j][i+1],L[j][i]-1);
			R[j][i+1]=min(R[j][i+1],R[j][i]+1);
		}
		for(i=202000;i>=0;i--) {
			U[j][i]=max(U[j][i],U[j][i+1]-1);
			D[j][i]=min(D[j][i],D[j][i+1]+1);
			L[j][i]=max(L[j][i],L[j][i+1]-1);
			R[j][i]=min(R[j][i],R[j][i+1]+1);
			if(D[j][i]<=U[j][i]) {
				add[D[j][i]].push_back(i);
				del[U[j][i]].push_back(i);
			}
		}
	}
	ll ret=0;
	FOR(i,202000) {
		FORR(a,add[i]) bt[i%2][a%2].add(a,1);
		FOR(j,2) if(R[j][i]<=L[j][i]) ret+=bt[i%2][R[j][i]%2](L[j][i])-bt[i%2][R[j][i]%2](R[j][i]-1);
		FORR(a,del[i]) bt[i%2][a%2].add(a,-1);
	}
	cout<<ret<<endl;
	
	
}

まとめ

字で説明するの非常にめんどう。