코드잼 2020 라운드 1B 후기

코드잼 예선을 통과하고, 라운드 1을 응시하게 되었습니다.

라운드 1은 A, B, C 로 나뉘어 진행됩니다.

세 라운드 중 어느 것이라도 1500등 안에 들어가면 통과입니다.

한 서브 라운드라도 합격하면 이후 라운드는 응시할 수 없습니다.

따라서 1A 보다 1B가, 1B보다는 1C가 등수 이내에 들기 쉽습니다. 아무래도 잘하는 사람은 먼저 라운드에 응시해서 바로 다음 라운드 티켓을 거머쥘 수 있기 때문이겠죠.

1A는 저번주 일요일 아침에 시행되었습니다. 1번 문제에서 헤맨 나머지 그렇게 많이 문제를 풀지 못했고..

1번 스몰 인풋, 2번 미들 인풋까지 풀어 19점, 5772등으로 마감했습니다.

1B는 어제 새벽에 시행되었습니다. 이번 라운드도 어렵긴 마찬가지였는데...

특히 1번 문제가 쥐약이었습니다.

1번 라지, 2번 스몰까지 풀어서 32점, 1892등으로 막을 내렸습니다.

 

 

2번 미들 인풋까지 긁었으면 아슬아슬하게 통과할 수 있었을 텐데 아쉽습니다.

1번에서 좋은 생각을 하지 못하여 한시간 반이나 헤맸고... 2번은 그래서 뭐 거의 손도 못댄 것이 원인이었습니다.

꾸준히 문제를 풀어서 실력을 향상시켜야 할 것 같습니다.

 

1번 Expogo

 

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b62

Code Jam - Google’s Coding Competitions

풀긴 풀어서 답을 냈습니다.

a, b가 있다고 해 봅시다.

a, b의 절대값보다 약간 큰 2의 지수부터 시작합니다.

a, b 중 절대값이 큰 놈을 굴라서 해당하는 2의 지수를 적용해, 절대값이 줄어나가게 만듭니다.

예를 들어 a=2 b=3 이면,

4 → a=2, b=3-4=-1 (S)

2 → a=2-2=0 b=-1 (W)

1 → a=0 b=-1-(-1)=0 (N)

뻘짓 끝에 모든 풀이가 이런 식으로 하면 구할 수 있음을 알아냈습니다만,

왜 그런지는 증명하지 못했습니다.

 

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <set>
#include <bitset>
#include <cmath>
#include <climits>
#include <numeric>

#define INF 16000000
using namespace std;


typedef long long ll;


enum Direction {
    N, S, E, W
};

void print(vector<Direction> value) {

    ll x=0;
    ll y=0;

    for (ll i=0; i < value.size(); i++) {
        ll append = 1 << i;
        switch (value[i]) {
            case N:
                cout << "N";
                y += append;
                break;
            case S:
                cout << "S";
                y -= append;
                break;
            case E:
                cout << "E";
                x += append;
                break;
            case W:
                cout << "W";
                x -= append;
                break;
        }

    }

    cout << '\n' << x << ' ' << y << '\n';

}


pair<bool, vector<Direction>> solve(ll startIndex, ll a, ll b) {

    vector<Direction> value;

    for (ll i = startIndex; i>=0; i--) {
        ll append = 1 << i;

        if (abs(a) < abs(b)) {
            if (b > 0) {
                value.push_back(N);
                b -= append;
            } else {
                value.push_back(S);
                b += append;
            }
        } else {
            if (a > 0) {
                value.push_back(E);
                a -= append;
            } else {
                value.push_back(W);
                a += append;
            }
        }
    }
    std::reverse(value.begin(), value.end());


    if (a ==0 && b==0) {
        return {true, value};
    } else {
        return {false, value};
    }
    for (auto element: value) {
        switch (element) {
            case N:
                cout << "N";
                break;
            case S:
                cout << "S";
                break;
            case E:
                cout << "E";
                break;
            case W:
                cout << "W";
                break;
        }

    }


}

void brute_force(ll depths, vector<Direction> value) {

    if (depths == 0) {
        print(value);
        return;
    }

    for (ll i=0; i<4; i++) {
        auto nextValue = value;
        switch (i) {
            case 0:
                nextValue.push_back(N);
                break;
            case 1:
                nextValue.push_back(S);
                break;
            case 2:
                nextValue.push_back(E);
                break;
            case 3:
                nextValue.push_back(W);
                break;
        }
        brute_force(depths-1, nextValue);
    }

}
int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

//    vector<Direction> value;
//    brute_force(5, value);
//
    long long t;
    cin >> t;

    ll originT = t;
    while (t--) {

        ll a, b;

        cin >> a >> b;

        ll value = max(abs(a), abs(b));

        ll index = 0;

        while (true) {

            ll temp = 1 << index;
            if (temp > value) {
                break;
            } else {
                index++;
            }
        }

        bool hasAnswer = false;

        cout << "Case #" << originT - t << ": ";
        for (ll i=0; i<=32; i++) {
            auto answer = solve(i, a, b);
            if (answer.first) {
                for (auto element: answer.second) {
                    switch (element) {
                        case N:
                            cout << "N";
                            break;
                        case S:
                            cout << "S";
                            break;
                        case E:
                            cout << "E";
                            break;
                        case W:
                            cout << "W";
                            break;
                    }

                }
                hasAnswer = true;
                cout << "\n";

                break;
            }

        }


        if (!hasAnswer) {
            cout << "IMPOSSIBLE\n";
        }
    }
    return 0;

}

 

2번. Blindfolded Bullseye

 

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b63

인터랙티브 문제였는데, 남은 시간이 촉박하여 스몰 인풋만 공략했습니다.

스몰 인풋의 경우 가능한 원의 중점이 x= [-5,5] y= [-5,5] 내부이므로, 해당하는 경우를 전탐색하면 됩니다.

미들 인풋을 풀려면 이진 탐색이 들어가야 하는 것 까지는 생각을 했는데,

빠르게 구현할 자신이 없어서 우물쭈물하다가 끝났습니다.

라지까지는 어떻게 나중에라도 풀어볼 생각입니다.

 

 

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <set>
#include <bitset>
#include <cmath>
#include <climits>
#include <numeric>

#define INF 16000000
using namespace std;


typedef long long ll;

int main() {
//    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    long long t;
    cin >> t;

    ll a, b;

    cin >> a >> b;

    while (t--) {

        bool hasAnswer = false;

        for (ll i=-5; i<=5; i++) {
            if (hasAnswer) {
                break;
            }
            for (ll j=-5; j<=5; j++) {
                cout << i << ' ' << j << '\n';
                cout.flush();
                string result;
                cin >> result;

                if (result == "CENTER") {
                    hasAnswer = true;
                    break;
                }
            }
        }
    }
    return 0;

}

 

3번 Join the Ranks

 

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b64

Code Jam - Google’s Coding Competitions

문제 영어 지문부터 길어서 읽지도 않았습니다.

 

 

경험과 잔머리가 딸려서 빨리빨리 못 푼 것이 아쉽습니다.

연습을 많이 해야 되겠습니다. 인생을 날로 먹고 싶은데 그런 마인드를 방해하는 적폐들이 많아 문제입니다.

 

추신: 1번의 제목, 엑스포고는 뭘까요...? 사전 찾아보긴 귀찮네요.

주변의 많은 분들이 1번 내용 읽고 "아 이건 내가 풀 게 아니구나" 하고 생각하고 바로 꿀잠 잤다고 합니다.

뜻을 알 수 없는 제목이 그 원인으로도 한몫을 한 것 같습니다.