Codeforces #737 Div2 : E. Assiut Chess

あいにく本番に解けず。
https://codeforces.com/contest/1557/problem/E

問題

チェスを題材にしたインタラクティブ問題である。
先手は初手でクイーンをどこかに配置し、相手は、キングをどこかに配置する。
相手がキングを置いた位置は与えられない。

以後、両者交互に駒を動かす。
ただし、相手は、次の手でクイーンが移動可能なマスに移動することができるような移動はできない。
相手の駒は、移動した向きだけ与えられて具体的な位置が与えられないとき、130ターン以内に相手が移動不可能となるようにせよ。

解法

クイーンを一番上の段に置き、キングを最下段に追い詰めよう。
キングがクイーンより2段以上下にいることが確定する場合、クイーンを1段下げる。
それを確定させるため、クイーンを以下のように動かそう。

• クイーンを左から右または右から左に1マスずつ動かす。
  • もしキングが間に上方向に動かない場合、キングは2段以上下にいることが確定する。
  • もしキングが下方向に動いた場合、キングは2段以上下にいることが確定する。
  • もしキングが上方向に動いた場合、クイーンをまた左右端に戻して再度走査しよう。上に行ける回数は限度があるので、何度もこれを行われることはない。

int T;

string go(int y,int x) {
	cout<<(y+1)<<" "<<(x+1)<<endl;
	string s;
	cin>>s;
	return s;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		x=y=0;
		s=go(y,x);
		if(s=="Done") continue;
		
		int turn=0;
		while(1) {
			int up=0;
			
			FOR(i,7) {
				if(turn==0) x++;
				else x--;
				s=go(y,x);
				if(s=="Done") break;
				if(s.substr(0,2)=="Up") up++;
				if(s.substr(0,2)=="Do") {
					y++;
					s=go(y,x);
					if(s=="Done") break;
					up=-1;
					break;
				}
			}
			
			if(up==-1) {
				if(x==0) {
					turn=0;
				}
				else if(x==7) {
					turn=1;
				}
				else {
					x=0;
					s=go(y,x);
					if(s=="Done") break;
					turn=0;
				}
				continue;
			}
			
			if(i<7) break;
			if(up<=0) {
				y++;
				s=go(y,x);
				if(s=="Done") break;
			}
			turn^=1;
		}
		
	}
}

まとめ

過去にどこかで出ていてもおかしくない題材。