Codeforces #1046 : Div1. B. For the Champion

そこそこの出来だった回。
https://codeforces.com/contest/2135/problem/B

問題

二次元座標系において、ロボットの初期位置を当てるインタラクティブ問題である。
まず、N個のアンカー点の座標が与えられる。
以下のクエリを10回まで使い、初期位置を当てよ。

• ロボットを、上下左右のいずれか、指定した距離だけ移動する。その後、各アンカー点までのマンハッタン距離の最小値を返す。

解法

アンカー点のbounding boxの右上と右下に移動すれば、移動後のロボットのX座標がわかり、そこからY座標も求められる。

int T,N;
ll X[101],Y[101];
ll D[2],C;
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll XpY=-1LL<<40;
		ll XmY=-1LL<<40;
		FOR(i,N) {
			cin>>X[i]>>Y[i];
			XpY=max(XpY,X[i]+Y[i]);
			XmY=max(XmY,X[i]-Y[i]);
		}
		ll v=1000000000;
		FOR(i,2) {
			cout<<"? R "<<v<<endl;
			cin>>D[0];
		}
		FOR(i,2) {
			cout<<"? U "<<v<<endl;
			cin>>D[0];
		}
		FOR(i,4) {
			cout<<"? D "<<v<<endl;
			cin>>D[1];
		}
		ll a=D[0]+XpY-4*v;
		ll b=D[1]+XmY-4*v;
		ll RX=(a+b)/2;
		ll RY=(a-b)/2;
		
		cout<<"! "<<RX<<" "<<RY<<endl;
		
	}
}

まとめ

これは割とすんなり解けた。