Codeforces #877 : Div2 F. Stuck Conveyor

こういうのどこからどう手を付けるかよくわからない。
https://codeforces.com/contest/1838/problem/F

問題

N*Nのグリッドを考える。
外周部以外の各マスには、上下左右のいずれかを差す矢印が書かれているとする。
どこかのマスに駒を置くと、矢印に沿って隣接マスに移動し、無限ループで動き続けるか外周部に到達して止まる。

ここで各マスの矢印の向きを任意に指定し、また駒の初期位置を定めると、駒がどこに到達するかわかるクエリが使えるとする。
ただし、1マスだけは矢印の向きをどう指定しても、それが無視されて固定の向きにされる。
クエリを駆使し、固定の向きとなるマスの位置とその向きを答えよ。

解法

まず左上から右下にジグザグに降りるパターンと右下から左上にジグザグに上がるパターンを尋ねる。
どちらかのパターンで無限ループに入る。
あとは二分探索で、ジグザグパターンの途中を書き換えて早めに外周部に誘導するようにすることで、固定マスを特定できる。

固定マスが特定できれば、その向きは2択のうち片方なので、両方試してみればよい。

int N;
int id[102][102];
vector<pair<int,int>> S;
string G[101];



void grid() {
	int y,x;
	FOR(y,N) G[y].resize(N);
	int i;
	FOR(i,S.size()-1) {
		if(S[i+1].first>S[i].first) G[S[i].first-1][S[i].second-1]='v';
		if(S[i+1].first<S[i].first) G[S[i].first-1][S[i].second-1]='^';
		if(S[i+1].second<S[i].second) G[S[i].first-1][S[i].second-1]='<';
		if(S[i+1].second>S[i].second) G[S[i].first-1][S[i].second-1]='>';
	}
}



pair<pair<int,int>,char> ask(int id) {
	cout<<"? "<<S[id].first<<" "<<S[id].second<<endl;
	int y,x;
	FOR(y,N) {
		FOR(x,N) cout<<G[y][x];
		cout<<endl;
	}
	cin>>y>>x;
	if(y==-1) return {{-1,-1},'L'};
	if(y==0) return {{1,x},'^'};
	if(y==N+1) return {{N,x},'v'};
	if(x==0) return {{y,1},'<'};
	if(x==N+1) return {{y,N},'>'};
	return {{0,0},0};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	i=0;
	FOR(y,N) {
		FOR(x,N) {
			k=x;
			if(y%2) k=N-1-k;
			id[y][k]=i++;
			S.push_back({y+1,k+1});
		}
	}
	S.push_back({N+1,S.back().second});
	grid();
	auto p=ask(0);
	if(p.second!='L') {
		S.pop_back();
		reverse(ALL(S));
		S.push_back({0,S.back().second});
		grid();
		p=ask(0);
	}
	
	if(p.second=='L') {
		int L=0,R=S.size()-1;
		while(L+1<R) {
			int M=(L+R)/2;
			p=ask(M);
			if(p.second=='L') L=M;
			else R=M;
		}
		
		int ty=S[L].first-1,tx=S[L].second-1;
		FOR(y,N) FOR(x,N) {
			if(y<ty) G[y][x]='^';
			else if(y>ty) G[y][x]='v';
			else if(x<tx) G[y][x]='<';
			else if(x>tx) G[y][x]='>';
		}
		p=ask(L);
		p.first.first=ty+1;
		p.first.second=tx+1;
	}
	cout<<"! "<<p.first.first<<" "<<p.first.second<<" "<<p.second<<endl;
}

まとめ

解答を聞いてしまうとすんなりなんだけどねぇ。