kmjp's blog

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

Codeforces #577 Div2 E2. Knightmare (hard)

Codeforces

なんか問題設定がややこしい問題。
https://codeforces.com/contest/1201/problem/E2

問題

チェス盤と白黒のナイトを使ったゲームを行い。
チェス盤のサイズは、縦横偶数とする。
初期状態で白黒ナイトが異なるマスにおかれている。

プレイヤーは白黒どちらのナイトを使うか選択できる。
以後、白ナイトの手番の方から交互に自身のコマを動かす。
各手番ではナイトと同じ移動を取れる。

各自勝利条件は以下の通り。

  • 自分の手番で自身の駒を相手の駒のマスに移動出来たら勝ち。
  • ゴールマスに到着すること。白黒ゴールマスはチェス盤の中央にあるが、白黒で1マスずれている
    • その際、ゴールマスに到着して次の相手ターン完了までに相手に覆いかぶされないことが必要。

白黒好きな方を選択し、必勝法を示せ。

解法

相手がゴールに到達、または自身のゴール後、次の相手ターンで相手が覆いかぶさってこないのが確定している色があった場合、そちらを選んでゴールに向かえばよい。

以下、それ以外の場合を考える。
この設定ではあとを追う方が有利である。
1回移動するとマス目のパリティが変化するため、相手に覆いかぶさられる可能性のある方は常に固定される。
よって、覆いかぶさられない方を選択しよう。

まずは相手ゴールに向かう。
相手が余裕をもってゴールするケースは最初に排除しているので、相手に左記にゴールされることはない。
もし相手が先に相手のゴールマスについた場合、次の自身の番で覆いかぶさって勝ちである。
そうではない場合、相手はゴールに3手以上かかる場所にいることになるので、そこから自身のゴールに急転しよう。
自分の方が先にゴールに着く。

int D[2][1010][1010];
pair<int,int> from[2][1010][1010];
int H,W;
int X1,X2,Y1,Y2;
int TX,TY1,TY2;
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	FOR(y,H+1) FOR(x,W+1) D[0][y][x]=D[1][y][x]=1<<30;
	
	queue<int> Q;
	TY1=H/2;
	TY2=H/2+1;
	TX=W/2;
	D[0][TY1][TX]=0;
	D[1][TY2][TX]=0;
	Q.push(0*4000000+(TY1)*2000+TX);
	Q.push(1*4000000+(TY2)*2000+TX);
	while(Q.size()) {
		int id=Q.front()/4000000;
		int cy=Q.front()/2000%2000;
		int cx=Q.front()%2000;
		Q.pop();
		
		FOR(i,8) {
			int tx=cx+dx[i];
			int ty=cy+dy[i];
			if(tx<1 || tx>W || ty<1 || ty>H) continue;
			
			if(D[id][ty][tx]>D[id][cy][cx]+1) {
				D[id][ty][tx]=D[id][cy][cx]+1;
				Q.push(id*4000000+ty*2000+tx);
				from[id][ty][tx]={cy,cx};
			}
		}
	}
	
	cin>>Y1>>X1>>Y2>>X2;
	
	
	if(D[0][Y1][X1]+1<=D[0][Y2][X2] && D[0][Y1][X1]<=D[1][Y2][X2]) {
		cout<<"WHITE"<<endl;
		while(X1!=TX || Y1 !=TY1) {
			auto a=from[0][Y1][X1];
			X1=a.second;
			Y1=a.first;
			cout<<Y1<<" "<<X1<<endl;
			if(X1==TX&&Y1==TY1) return;
			cin>>y>>x;
		}
		return;
	}
	if(D[1][Y2][X2]+2<=D[1][Y1][X1] && D[1][Y2][X2]+1<=D[0][Y1][X1]) {
		cout<<"BLACK"<<endl;
		cin>>y>>x;
		while(X2!=TX || Y2 !=TY2) {
			auto a=from[1][Y2][X2];
			X2=a.second;
			Y2=a.first;
			cout<<Y2<<" "<<X2<<endl;
			if(X2==TX&&Y2==TY2) return;
			cin>>y>>x;
		}
		return;
	}
	if((X1+Y1)%2==(X2+Y2)%2) {
		cout<<"BLACK"<<endl;
		cin>>Y1>>X1;
		if(D[1][Y2][X2]>D[0][Y1][X1]) {
			while(Y2!=TY1 || X2!=TX) {
				if(abs(Y1-Y2)+abs(X1-X2)==3 && abs(Y1-Y2)>=1&&abs(Y1-Y2)<=2) {
					cout<<Y1<<" "<<X1<<endl;
					return;
				}
				auto a=from[0][Y2][X2];
				X2=a.second;
				Y2=a.first;
				cout<<Y2<<" "<<X2<<endl;
				cin>>Y1>>X1;
			}
		}
		if(abs(Y1-Y2)+abs(X1-X2)==3 && abs(Y1-Y2)>=1&&abs(Y1-Y2)<=2) {
			cout<<Y1<<" "<<X1<<endl;
			return;
		}
		while(1) {
			auto a=from[1][Y2][X2];
			X2=a.second;
			Y2=a.first;
			cout<<Y2<<" "<<X2<<endl;
			if(Y2==TY2&&X2==TX) return;
			cin>>Y1>>X1;
		}
	}
	else {
		cout<<"WHITE"<<endl;
		if(D[0][Y1][X1]>D[1][Y2][X2]) {
			while(Y1!=TY2 || X1!=TX) {
				if(abs(Y1-Y2)+abs(X1-X2)==3 && abs(Y1-Y2)>=1&&abs(Y1-Y2)<=2) {
					cout<<Y2<<" "<<X2<<endl;
					return;
				}
				auto a=from[1][Y1][X1];
				X1=a.second;
				Y1=a.first;
				cout<<Y1<<" "<<X1<<endl;
				cin>>Y2>>X2;
			}
		}
		if(abs(Y1-Y2)+abs(X1-X2)==3 && abs(Y1-Y2)>=1&&abs(Y1-Y2)<=2) {
			cout<<Y2<<" "<<X2<<endl;
			return;
		}
		while(1) {
			auto a=from[0][Y1][X1];
			X1=a.second;
			Y1=a.first;
			cout<<Y1<<" "<<X1<<endl;
			if(Y1==TY1&&X1==TX) return;
			cin>>Y2>>X2;
		}
	}
	
	
}

まとめ

理屈はわかるけど実装はかなりめんどい。