yukicoder : No.513 宝探し２、No.514 宝探し３

最初から514相当の解法を取ってしまった。
http://yukicoder.me/problems/no/514

問題

２次元座標上で(0,0)-(10^9,10^9)の矩形の範囲のどこかの格子点に宝が埋められている。
座標を指定すると、宝のある位置までのマンハッタン距離を答えるクエリを最大20回用いて宝の位置を特定せよ。

No.513では座標の範囲が狭く、クエリの最大許容回数が多い以外の違いはない。

解法

ある点からマンハッタン距離が一定の点は菱形状の形状を成すことに留意すると、クエリを2回投げるだけで求められる。
(２つの菱形の交点を求めればよい)

(0,0)からの距離Aと(0,10^9)からの距離Bを問い合わせよう。
仮に宝が(X,Y)にある場合、前者はX+Y、後者はX+(10^9-Y)を返すので、ここからX,Yを求められる。

int ask(int x,int y) {
	int ret;
	cout<<x<<" "<<y<<endl;
	cin>>ret;
	if(ret==0) exit(0);
	
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int A=ask(0,0);
	int B=ask(0,1000000000);
	int X=(A+B-1000000000)/2;
	int Y=A-X;
	
	ask(X,Y);
}

まとめ

513が終わって★３だと思って514を身構えつつ開いたら、同じ解法で解けたのでびっくり。