第3回 ドワンゴからの挑戦状 本選: C - ドワンGo
solution
- とりあえずテレビちゃんに近い$1$点を見つける
- 空間を円に内接する$R\sqrt{2} \times R\sqrt{2}$の長方形に切ってしらみつぶしにやる
- テレビちゃんを円周上に乗せる点を$2$つ見つける
- ふつうに二分探索
- 一方の軸$x$は固定してこれと共に条件を満たす$y_1,y_2$を見つけると後が楽
- 見つけた$2$円の交点の周囲を試す
- 三平方の定理とかでいい感じにする
基本的には上でよい。ただしときおり誤差で失敗する。 テレビちゃんを円周上に乗せる点を$(y_1,x), (y_2,x)$としたとき、$y_t \approx \frac{y_1 + y_2}{2}$とすれば誤差は$\pm 1$程度だが、$x_t \approx x \pm \sqrt{R^2 - {|y_1 - y_2|}^2}$の誤差は大きい。 この$x_t$の誤差が大きくなるのは特に$\sqrt{R^2 - {|y_1 - y_2|}^2}$が小さいときであるというのが観察から分かる。 そこで、1.と2.の間で適当に$x \gets x + \alpha$とするなどして、テレビちゃんを$x$軸方向に見て端に追い遣っておくとよい。
implementation
手元テスト用 ジャッジコード
#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import random
import sys
import argparse
L = 1000000
R = 100000
xt = random.randint(0, L)
yt = random.randint(0, L)
log.info('xt = %d', xt)
log.info('yt = %d', yt)
parser = argparse.ArgumentParser()
parser.add_argument('binary', nargs='?', default='./a.out')
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level
p = process(args.binary, stderr=sys.stderr)
for q in range(200):
try:
x, y = map(int, p.recvline().split())
except:
log.failure('RE')
sys.exit(1)
if x == xt and y == yt:
p.sendline('found')
log.success('AC')
log.info('%d queries used', q+1)
sys.exit(0)
if (xt - x) ** 2 + (yt - y) ** 2 < R ** 2:
p.sendline('close')
else:
p.sendline('far')
p.sendline('kill')
log.failure('QLE')
sys.exit(1)
回答
#include <iostream>
#include <cmath>
#include <functional>
#include <random>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
int binsearch(int l, int r, function<bool (int)> p) { // [l, r), p is monotone
assert (l < r);
-- l; -- r; // (l, r]
while (l + 1 < r) {
int m = (l + r) / 2;
// (p(m) ? r : l) = m;
bool it = p(m) ;
assert ((it ? r : l) != m);
(it ? r : l) = m;
}
return r; // = min { x | p(x) }
}
const int L = 1000001;
const int R = 100000;
const int l = R * sqrt(2) - 3;
bool query(int y, int x) {
cout << x << ' ' << y << endl;
cout.flush();
string s; cin >> s;
if (s == "found") exit(0);
if (s == "close") return true;
if (s == "far") return false;
assert (false);
}
pair<int,int> find_close() {
default_random_engine gen((random_device()()));
uniform_int_distribution<int> dist(- R/20, 0);
for (int y = dist(gen); y < L; y += l) {
for (int x = dist(gen); x < L; x += l) {
if (query(y + l/2, x + l/2)) {
return { y + l/2, x + l/2 };
}
}
}
assert (false);
}
int main() {
int y, x; tie(y, x) = find_close();
repeat (i,20) {
if (query(y, x+R/10)) {
x += R/10;
} else {
if (query(y+R/10, x)) {
y += R/10;
} else if (query(y-R/10, x)) {
y -= R/10;
} else {
break;
}
}
}
int y1 = binsearch(y, y+2*R+1, [&](int y) { return not query(y, x); });
int y2 = binsearch(y-2*R, y+1, [&](int y) { return query(y, x); });
int dy = y1 - y2;
int dx = sqrt(pow(R, 2) - pow(dy/2.0, 2));
repeat_from (i, -1, 1+1) {
repeat_from (j, -5, 5+1) {
for (int pm : { +1, -1 }) {
query((y1 + y2) / 2 + i, x + pm*dx + j);
}
}
}
return 1;
}