Google Code Jam2020 Round1B参加記

今更ですが、GCJ R1Bが4/20 午前1:00（！）にあったので出場しました。流石に時間が遅いので出るか迷いましたが、別にレートがつくわけではないので（ABCもレートがつきませんでしたね）、爆死しても損はないと言うことでダメもとで出場しました。

結果

845位と言うことで、無事通過できました！ A問題のテストセット1、2と、B問題をフルマークして合計47点でした。Aはlargeを解きに行こうとして全くの嘘をやっていたので全く通らず、最終的に終了10分前にsmallを通すためのBFSシミュレーションでゴリ押しました。

Bの解説だけ以下記述します。

B問題

概要

2e9四方の正方形盤と、半径がA以上B以下の円形の的が与えられる。あなたは300回まで座標を指定して、そこが的の中心(CENTER)か、的の丸の中(HIT)か、丸の外かの情報を得ることができる。的の中心の座標（CENTER)を得よ。

GCJのインタラクティブ問題はテストランナースクリプトがpythonで与えられるのですが、自分はこのスクリプトの使い方がわからずqualからずっと放置していました。結局terminalで手でテストして送りました。

解法

この問題は制約が最大の本質で、Hiddenの制約を見ると与えられる半径は5e8以上1e9以下とあるので、(±5e8 or 0,±5e8 or 0)の 9点のいずれか一つは必ずHITになることがわかります。

まず1つのHITを得られた点を(X,Y)としましょう。そうすると、直線x = Xの上で、Xより左側とXより右側に「HITとMISSの境界」がただひとつ存在することがわかるので、その境界を二分探索して求めます。左側の境界をL、右側の境界をRとしましょう。すると、円の中心のx座標Cxは(R + L)/2として求められます。y座標についても同様に求めれば良いです。

//52行目から編集
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;}
template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;}
///////////////////////////////////////////////////////////

string s;//judge

long long candr = 1e9 / 2;
long long candx[9] = {0,1,1,0,-1,-1,-1,0,1};
long long candy[9] = {0,0,-1,-1,-1,0,1,1,1};
ll X,Y;

bool output(ll x,ll y){
    cout << x << ' ' << y << '\n';
    cout << flush;

    cin >> s;
    if(s == "CENTER")return true;
    else return false;
}
void main2(){

    // 9箇所のポイントを全部試す
    for(int i = 0;i < 9;i++){
        ll x = candr * candx[i];
        ll y = candr * candy[i];

        if(output(x,y)){
            return;
        }else if(s == "HIT"){
            X = x,Y = y;
            break;
        }
    }
    //(x,y)から上下の境界ポイントを二分探索する
    ll ub = 1e9,lb = Y;
    while(lb + 1 != ub){
        ll mid = (lb + ub)/2;
        if(output(X,mid)){
            return;
        }else{
            if(s == "HIT"){
                lb = mid;
            }else{
                ub = mid;
            }
        }
    }

    ll CYU = lb;
    ub = Y,lb = -1e9;
    while(lb + 1 != ub){
        ll mid = (lb + ub)/2;
        if(output(X,mid)){
            return;
        }else{
            if(s == "HIT"){
                ub = mid;
            }else{
                lb = mid;
            }
        }
    }
    ll CYD = ub;

    ll ansY = (CYU + CYD)/2;


     ub = 1e9,lb = X;
    while(lb + 1 != ub){
        ll mid = (lb + ub)/2;
        if(output(mid,Y)){
            return;
        }else{
            if(s == "HIT"){
                lb = mid;
            }else{
                ub = mid;
            }
        }
    }

    ll CXU = lb;
    ub = X,lb = -1e9;
    while(lb + 1 != ub){
        ll mid = (lb + ub)/2;
        if(output(mid,Y)){
            return;
        }else{
            if(s == "HIT"){
                ub = mid;
            }else{
                lb = mid;
            }
        }
    }
    ll CXD = ub;

    ll ansX = (CXU + CXD)/2;
    output(ansX,ansY);
}


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);


    int testcase;cin >> testcase;
    ll a,b;cin >> a >> b;
    for(int i = 1;i <= testcase;i++){
        main2();
    }
    return 0;
}
/*
 *!!CHECK!! 
 * 制約をよく読め：まず最も愚直な解法を考えろ
 * intの掛け算をしてる場合：overflowは大丈夫？
 * 制約の下限・上限は大丈夫？
 * 木構造は一直線にした時TLEしない？
 * */

次回Round2は5月？にあると思うので、せっかくのチャンスなので、Tシャツを目指して頑張ろうと思います。