Google Codejam 2020 Round 1B 1, 2번 풀이

Codejam은 구글에서 진행하는, 기업 대회 중에서는 가장 규모도 크고 알려진 PS 대회로 수만명이 참가하는 대회이다.

Qualification Round에서 기본적인 코딩 실력 정도로 거르고, 그 인원으로 Round 1을 세 번 치르는데 세 번 중 한 번만 1500등 안에 들면 Round 2에 진출할 수 있다. 1A에서 진출한 사람은 1B를 응시하지 못하므로 1A, 1B, 1C로 갈수록 진출하기는 조금 쉬워진다고 할 수 있겠다.

 

Round 1A같은경우는 아침이라 말려서 (라는 핑계로) 2천등 정도 해서 진출에 실패했고, Round 1B는 어제 새벽에 319등이라는 기대 이상의 좋은 성적을 거두고 진출했다. 

푸는데 성공한 두 문제의 풀이를 적으려고 한다. Editorial 과 거의 같지만, 1번의 아이디어가 약간 다르다.

 

I. Expogo

$i$ 번째 점프로는 $2^{i-1}$ 만큼 상하좌우중 하나로 이동할 수 있다고 하자. 이때, 주어진 점까지 갈 수 있겠는지, 갈 수 있다면 최소한 횟수로 어떻게 가야 하는지를 찾는 문제. 타겟이 되는 '이동 벡터'를 $(x, y)$ 라고 하자. 구체적으로, 증명의 편의를 위해 $(x, y)$ 를 '남은 이동량' 이라고 생각하고 이를 $(0, 0)$ 으로 줄인다는 목표를 갖자.

 

아이디어 1 : 작은 경우를 몇 개 해보자. 먼저 관찰할 수 있는 것은, $\abs{x} + \abs{y}$ 가 짝수면 아예 희망이 없다.

아이디어 2 : 최소한 몇번은 필요한지 lower bound를 잡자. 자명한 것은, $2^{n-1} \leq \abs{x} + \abs{y} < 2^n$ 인 점을 향해 가기 위해서는 $n$ 번은 가야 한다. (최대한 잘 가더라도, $k$ 번의 점프로는 최대 $2^{k}-1$ 의 거리만 이동할 수 있으므로)

 

그리고 다음 보조정리도 필요하다. 몇가지 경우를 잘 해봤다면 관찰할 수 있다.

Lemma. $n$번에 이동할 수 있다면, $n$보다 큰 $m$번에는 반드시 이동할 수 있다.

Proof. $2^{n} = 2^{m} - 2^{m-1} - 2^{m-2} - \dots - 2^{n}$. 

 

이제, 다음과 같은 놀라운 주장을 편다.

주장 : $2^{n-1} \leq \abs{x} + \abs{y} < 2^n$ 인 '홀수 점' ($\abs{x}+\abs{y}$ 가 홀수) 에는 항상 $n$번에 갈 수 있다. 

즉, 항상 아이디어 2에서 잡은 Lower bound를 충족하는 해가 존재한다는 주장이다.

 

증명 (별로 Rigorous하지는 않지만, 아이디어를 가져가자) : 수학적 귀납법을 거꾸로 쓴다는 생각을 하자.

일반성을 잃지 않고, $\abs{x} \geq \abs{y}$ 를 가정하자 (그렇지 않다면 매번 뒤집으면 그만이다). 이때, $x$에 $2^{n-1}$ 을 더하거나 빼자. 방향은 $\abs{x}$ 가 작아지는 방향으로 가기로 하자 ($x$가 음수이면 더하고 양수이면 뺀다).

이때, $2^{n-2} < \abs{x} < 2^{n}$ 인것이 당연하고 ($x$쪽의 절댓값이 크다는것을 가정했다), $2^{n-2} < \abs{x} < 2^{n-1}$ 이었다면 $\abs{x'}<2^{n-2}$가 된다는 사실을 계산할 수 있으며, $2^{n-2} < \abs{y} < 2^{n-1 }$ 이므로 둘을 다시 더하면 $\abs{x'} + \abs{y'} < 2^{n-1}$ 로 줄어든다.

만약 $2^{n-1} < \abs{x} < 2^{n}$ 이었다면, $x$에 수행한 연산이 그대로 abs의 합을 줄이는 방향으로 작용하므로$\abs{x'} + \abs{y} < 2^{n-1}$ 로 줄어든다.

이제, 다음 Step부터는 굳이 '최소 스텝'을 밟지 않아도 된다 (이미 횟수를 확정해 버렸으므로). 이제 Lemma를 적용하면, $\abs{x'} + \abs{y} < 2^{n-1}$인 $x', y$ 를 $n-1$ 스텝에 밟을 수 있다. 

 

경계조건으로 절댓값의 합이 1인 경우 같은걸 잡아줘야 하는데, 항상 한번의 움직임으로 1만큼 이동이 가능하다.

위 증명을 그대로 코딩하면 된다. 

 

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

void solve()
{
    int x, y;
    cin >> x >> y;
    vector <int> xdir, ydir;
    int ax = -x, ay = -y;
    int sum = ax+ay;
    int bit = -1;
    vector <pii> move;
    int ms = 0;
    while(ms < abs(ax)+abs(ay))
    {
        bit++;
        ms += (1ll<<bit);
    }
    if (sum %2 == 0)
    {
        cout << "IMPOSSIBLE" << '\n'; return;
    }
    while(ax != 0 || ay != 0)
    {
        int u = (1ll<<bit);
        if (abs(ax)>=abs(ay))
        {
            if (ax>0)
            {
                xdir.push_back(-u);
                ax -= u;
            }
            else if (ax<0)
            {
                xdir.push_back(u);
                ax += u;
            }
        }
        else if (abs(ax)<abs(ay))
        {
            if (ay>0)
            {
                ydir.push_back(-u);
                ay-=u;
            }
            else if (ay<0)
            {
                ydir.push_back(u);
                ay += u;
            }
        }
        bit--;
    }
    for (auto it:xdir)
        move.push_back({it, 0});
    for (auto it:ydir)
        move.push_back({it, 1});
    sort(all(move),[](auto a, auto b)->bool{return abs(a.first)<abs(b.first);});
    for (auto it:move)
    {
        if (it.second==0)
            cout << (it.first>0?'E':'W');
        else
            cout << (it.first>0?'N':'S');
    }
    return;
}

int32_t main()
{
    usecppio
    int TC; cin >> TC;
    for (int tc = 1; tc<=TC; tc++)
    {
        cout << "Case #" << tc << ": ";
        solve();
        cout << "\n";
    }
}

 

II. Blindfold Bullseye

20억 * 20억 칸의 거대한 격자에, 반지름이 $A$ 이상 $B$ 이하의 정수인, 정수 격자점을 중심으로 하는 원이 있다.

여기에 우리는 '질문' 을 하고 '답' 을 들을 수 있는데,

'질문'은 $(x, y)$로 질문하고, 그에 대한 답은 MISS, HIT, CENTER 중 하나로 돌아온다. 각각 원 밖, 원 안, 중심을 의미하고, 중심을 찾으면 성공했으므로 다음 케이스로 넘어간다.

이때, 300번 이내의 질문으로 중심을 찾는 문제. 

 

중요한 조건으로, 문제를 읽어 보면 생각보다 원이 많이 크다는 것을 알 수 있다. 아무리 작아도 반지름이 5억인데, 20억*20억칸의 격자에 반지름이 5억인 원을 집어넣으면 거의 1/4 가까이 차게 된다. (정확히는 $\pi/16$). 이외에는 반지름이 얼마인지는 TC3을 풀어야 하는 입장에서는 전혀 도움이 되지 않는다 (TC2까지는 반지름의 상하한이 같아서, 이걸로 뭔가 하는거 같다. 잘 모르겠다)

 

즉, 처음에 100개정도 쿼리를 막 던지다 보면 원에 점이 하나 정도는 들어가게 된다. (랜덤하게 100번을 시도해서, 점이 한개도 안들어갈 확률이 엄청 낮다) 확률에 의존하지 않으려면, 나는 전체를 2억 칸씩 쪼개서 121개의 점을 찍은 다음 121개의 쿼리를 날렸는데 잘 생각해 보면 적어도 하나는 포함된다는 것을 알 수 있다. 

 

이제 한 점 $(x, y)$ 가 원에 포함된다고 했으니, 이 점으로부터 오른쪽, 왼쪽, 위, 아래 방향으로 무한히 직선을 뻗으면 이 점을 포함하는 어떤 연속적인 구간이 원에 포함되게 된다. 이 연속적인 구간을 $x$방향으로는 $(x_1, y)$ 부터 $(x_2, y)$ 라고 쓸 수 있고, $y$ 방향으로는 $(x, y_1)$, $(x, y_2)$ 로 쓸 수 있겠다. 즉, $([x_1, x_2], y)$ 는 '격자점만 봤을 때' 원의 현이고, $(x, [y_1, y_2])$ 도 현이다.

서로 평행하지 않은 두 현을 얻었으므로, 중심점의 좌표는 두 현의 수직이등분선의 교점, 즉 $x$좌표의 중점과 $y$좌표의 중점인 $(x_{mid}, y_{mid})$ 이다.

 

연속적인 구간을 찾기 위해서는, 한 점을 알고 있으므로 이분탐색을 이용하면 32번의 쿼리에 정확하게 경계를 잡을 수 있다. 즉, 4방향 * 32번의 쿼리이므로 많아야 130번의 쿼리로 해결할 수 있다.

 

코딩을 하다 보니 이분탐색에서 실수하기가 쉬운 것 같았다. 특히 '포함되는 최소' 좌표와 '포함되지 않는 최대' 좌표를 찾는 게 가장 실수하기 쉬운데, 1정도 차이가 나더라도 알아채기가 어렵고 무엇보다 이 문제 같은 경우는 테스팅할 방법이 마땅치 않아서 (정확한 값을 손으로 구하기가 매우 어렵기 때문에, off-by-1 에러를 잡기가 정말 힘들다) 디버깅이 정말 어렵다.

 

이 문제를 해결하기 위해, 지금까지 쓴 쿼리 횟수를 세 보자. 잘 보면 121개 + 130개 정도 썼으므로 대략 50개 정도 쿼리가 남았다는 것을 알 수 있다. 귀찮은 off-by-1을 처리하기 위해, 위 과정에서 구한 중심점을 중심으로 5*5 정사각형 정도를 모두 찍어보면 확실하게 답을 얻을 수 있고 귀찮은 생각을 할 필요가 없다.

 

import sys
t = 0
def interact(a, b):
    print(a, b)
    global t
    t += 1
    sys.stdout.flush()
    verdict = input()

    if verdict == "MISS":
        return 0
    elif verdict == "HIT":
        return 1
    elif verdict == "CENTER":
        return -1
    elif verdict == "WRONG":
        print("WRONG ANSWER")
        exit(0)
        
def main():
    global t
    t = 0
    M = 10**9
    C = M//5
    xcor = -1
    ycor = -1
    for i in range(-5, 6):
        for j in range(-5, 6):
            res = interact(C*i, C*j)
            if res == -1:
                return 
            elif res == 1:
                xcor = C*i
                ycor = C*j
    xlo = xcor
    xhi = 10**9+1
    xmid = (xlo+xhi)//2
    while xlo+1 < xhi:
        xmid = (xlo+xhi)//2
        res = interact(xmid, ycor)
        if res == -1:
            return
        elif res == 1:
            xlo = xmid
        else:
            xhi = xmid
    res = interact(xlo, ycor)
    if res == -1:
        return     
    if res == 0:
        xlo = xlo-1
    right = xlo
    xlo = -10**9
    xhi = xcor
    xmid = (xlo+xhi)//2
    while xlo+1 < xhi:
        xmid = (xlo+xhi)//2
        res = interact(xmid, ycor)
        if res == -1:
            return
        elif res == 1:
            xhi = xmid
        else:
            xlo = xmid    
    res = interact(xlo, ycor)
    if res == -1:
        return     
    if res == 0:
        xlo = xlo+1            
    left = xlo
    ylo = ycor
    yhi = 10**9+1
    ymid = (ylo+yhi)//2
    while ylo+1 < yhi:
        ymid = (ylo+yhi)//2
        res = interact(xcor, ymid)
        if res == -1:
            return
        elif res == 1:
            ylo = ymid
        else:
            yhi = ymid
    res = interact(xcor, ylo)
    if res == -1:
        return     
    if res == 0:
        ylo = ylo-1
    up = ylo
    ylo = -10**9
    yhi = ycor
    ymid = (ylo+yhi)//2
    while ylo+1 < yhi:
        ymid = (ylo+yhi)//2
        res = interact(xcor, ymid)
        if res == -1:
            return
        elif res == 1:
            yhi = ymid
        else:
            ylo = ymid    
    res = interact(xcor, ylo)
    if res == -1:
        return     
    if res == 0:
        ylo = ylo+1            
    down = ylo
    
    xans = (left+right)//2
    yans = (up+down)//2
    for i in range(-2, 3):
        for j in range(-2, 3):
            res = interact(xans+i, yans+j)
            if res == -1:
                return 
                
if __name__ == "__main__":
    T, A, B = map(int, input().split())
    t = 0
    for i in range(T):
        main()

---

R1A 망해서 느낌이 안좋았는데, 그래도 R1B에서 성공해서 다행이다. 작년 R1B를 천등 조금 넘게 통과했었기 때문에 설마 통과 못할까 싶긴 했지만...

목표는 일단 티셔츠 받기 (R3 진출) ㅋㅋ R2에서 봅시다 :)