코드잼 2020년 라운드 1C 후기

코드잼 라운드 1C는 황금연휴 한가운데 토요일 저녁에 열렸습니다.

1A는 아침에 열렸지만 상위권 참가자들이 몰려서 선방하지 못했고

1B는 새벽대에 열렸지만 고전했습니다.

마지막 1라운드인 1C는 한국기준 저녁 6시에 열렸습니다.

 

1A, 1B보다 문제가 평이했습니다.

일단 인터랙티브 문제가 없었던 게 난이도가 낮은 원인이 아니었나 싶습니다.

 

저는 1번, 2번 라지 인풋을 모두 푸니 합격 안정권에 들어갔습니다.

3번 스몰 인풋까지 풀고 30여분 남았으나, 3번 미들은 풀지 못했습니다.

 

 

결과는 800등선으로, 2라운드를 진출하게 되었습니다.

 

 

1. Overexcited Fan 극성 팬

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/0000000000317409

Code Jam - Google’s Coding Competitions

Peppurr 의 좌표와 이동 경로가 주어집니다.

극성팬은 한칸씩 움직이거나, 움직이지 않을 수 있습니다.

 

t가 지났을 때, Peppur와 극성팬의 최초 위치와의 택시 거리가, t 이하이면, t 시점에 극성팬과 Peppur가 만날 수 있습니다.

 

8분만에 풀수 있었고, 덕분에 2번 문제를 충분히 검토할 수 있었습니다.

#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;


ll solve(ll x, ll y, string buffer) {
    ll size = buffer.size();

    if (x == 0 && y == 0) {
        return 0;
    }

    for (ll i=0; i<size; i++) {
        switch (buffer[i]) {
            case 'S':
                y--;
                break;
            case 'N':
                y++;
                break;
            case 'E':
                x++;
                break;
            case 'W':
                x--;
                break;
        }

        if (abs(x) + abs(y) <= i+1){
            return i+1;
        }

    }
    return -1;
}

int main() {
    long long t;
    cin >> t;


    ll originT = t;

    while (t--) {

        ll x, y;
        cin >> x >> y;
        string temp;
        cin >> temp;

        auto answer = solve(x, y, temp);

        cout << "Case #" << originT - t << ": ";
        if (answer == -1) {
            cout << "IMPOSSIBLE" <<'\n';
        } else {
            cout << answer << '\n';
        }
    }
    return 0;

}

 

 

2. Overrandomized 과다 무작위 선택

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003179a1

Code Jam - Google’s Coding Competitions

 

라지 기준으로 설명하겠습니다.

유저가 랜덤하게 1부터 10^16-1 중 임의의 수 Mi를 선택합니다.

서버는 그에 따라서 닫힌 구간 [1, Mi] 에서 임의의 수 D를 선택합니다.

D의 각 자리수의 숫자를, 서버만 기억하고 있는 특정한 알파벳 문자로 치환하여, 유저에게 리턴합니다.

 

프로그램은 그 특정한 알파뱃 문자를 추론해야 합니다.

 

 

문제에서 제공한 입력을 보고, 알파벳이 총 몇 번 등장했는지 세는 프로그램을 작성했습니다.

주어진 건 빈도수밖에 없으니, 세 보는게 합리적이겠죠.

 

 

#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;


void solve(string a, string input, map<char, ll> &m) {

    for (auto c: input) {
        m[c]++;
    }

}


int main() {
    long long t;
    cin >> t;


    ll origll = t;

    while (t--) {
        ll u;
        cin >> u;

        map<char, ll> m;

        for (ll i=0; i<10000; i++) {

            string a; string input;
            cin >> a >> input;

            solve(a, input, m);

        }
        priority_queue<pair<ll, char>> pq;


        for (auto i: m) {
//            cout << i.first << ' ' << i.second << '\n';
            pq.push({i.second, i.first});
        }

        vector<char> answer;

        while (!pq.empty()) {
            answer.push_back(pq.top().second);
            pq.pop();
        }
//
//
        string output = "TPFOXLUSHB";
        for (auto c: output) {
            cout << c <<' ' << m[c] << '\n';
        }

        cout << "Case #" << origll - t << ": ";
        cout << answer[9];

        for (ll i=0; i<9; i++) {
            cout << answer[i];
        }

        cout << '\n';



    }
    return 0;

}

 

 

 

0이 제일 빈도가 작고, 1, 2, 3, 4,... 9 순으로 빈도가 높습니다.

 

나오는 문자열 빈도를 단순히 세서 정렬하면 될 것 같습니다.

 

두 자리에서는 먹혔는데, 열여섯 자리에서는 틀렸습니다.

 

열여섯 자리의 인풋을 생성해보고 빈도수를 세 보면 뭔가 건질 수 있겠습니다.

 

파이선으로 샘플 인풋을 작성해 보았습니다.

 

import random

def a():
  print(1)
  print(16)

  answer = "abcdefghij"

  for i in range(0, 10000):
    x = random.randint(1, 10000000000000000 - 1)
    print(x, end = " ")
    y = random.randint(1, x)
    stringY = str(y)
    for i in stringY:
      answerIndex = int(i) - 0
      print(answer[answerIndex], end = "")
    print("", end="\n")


if __name__ == '__main__':
  a()

 

샘플 인풋을 아까 작성한 프로그램에 돌려 보았습니다.

지나치게 개수가 균등하게 나타나고, 적절히 추론해낼 수 없습니다. 아까 풀이는 스몰 인풋에서만 통하는 것이 드러났습니다.

 

이 때, 저는 앞자리만 일단 세 보기로 했습니다.

앞자리에는 0에 해당하는 알파벳이 등장하지 않으므로, 그런 프로그램을 짜는 것 자체가 의미가 있을 것입니다.

적어도 0이 무엇인지 알 수 있으니까요.

 

의외의 수확을 할 수 있었습니다.

0은 없고, 1, 2, 3..., 9 순으로 빈도수가 나타납니다.

 

라지 인풋의 경우, 맨 끝자리의 빈도수만 세면 되는 것을 알아냈습니다.

 

아래 코드를 작성해 테스트에 통과했습니다.

 

#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;


void solve(string a, string input, map<char, ll> &m, map<char, ll> &first) {

    first[input[0]]++;
    for (auto c: input) {
        m[c]++;
    }

}




int main() {
    long long t;
    cin >> t;


    ll origll = t;

    while (t--) {
        ll u;
        cin >> u;

        map<char, ll> m;
        map<char, ll> first;
        for (ll i=0; i<10000; i++) {

            string a; string input;
            cin >> a >> input;

            solve(a, input, m, first);

        }

        char zero;
        priority_queue<pair<ll, char>> pq;


        map<char, ll> clone = first;
        for (auto e: m) {
            if (clone[e.first] == 0) {
                zero = e.first;
            }
        }



        for (auto i: first) {
            if (i.second > 0) {
//                cout << i.first << ' ' << i.second << '\n';
                pq.push({i.second, i.first});
            }

        }

        vector<char> answer;

        while (!pq.empty()) {
            answer.push_back(pq.top().second);
            pq.pop();
        }
//
//
//        string output = "TPFOXLUSHB";
//        for (auto c: output) {
//            cout << c <<' ' << m[c] << '\n';
//        }

        cout << "Case #" << origll - t << ": ";
        cout << zero;
//        cout << answer[9];
//
//        for (ll i=0; i<9; i++) {
//            cout << answer[i];
//        }

        for (auto e: answer) {
            cout << e;
        }

        cout << '\n';



    }
    return 0;

}

 

3. 너무 크게 만든 팬케이크 절단기

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003172d1

Code Jam - Google’s Coding Competitions

 

팬케이크 조각들이 N개 있고, 각각 Ai의 크기입니다.

다이너 D 명에게 팬케이크를 최소로 절단하여, 동일한 크기의 팬케이크 D개를 만들어 배분해야 합니다.

 

스몰 인풋의 경우, D이 2 혹은 3입니다.

스몰 인풋의 경우 가능한 모든 경우를 다 따져보기만 해도, 풀 수 있다고 생각합니다.

 

미들 인풋의 경우, D 가 조금 범위가 넓어서 일반적인 풀이가 필요합니다.

 

미들 인풋을 목표로 일반적인 코드를 작성해 보았습니다.

 

하지만 생각한 풀이가 스몰 인풋에선 맞았지만, 미들 인풋에서는 틀렸습니다.

 

코드는 맞게 구현했지만 알고리즘을 그릇되게 생각해 보입니다.

 

 

이때 30분 정도 남았는데 집중력이 많이 떨어진 상황이었습니다.

 

700등 정도 하고 있었는데... 라운드 2은 무리없이 통과할 정도였기도 합니다.

 

3번 문제는 미들을 풀지 못하고 시간이 종료되었습니다.

 

 

요약

 

이전에 응시한 1A, 1B에서 부진해, 1라운드에서 탈락할 줄 알았습니다.

다행히 1C에서 선방하여 2라운드까지 올라가게 되었습니다.

과거 3라운드는 주변에 올라간 전례가 없고, 2라운드에서 1000등 안에 입상한 분들은 좀 있습니다.

2라운드에 1000등안에 들면 구글에서 티샤츠를 보내 줍니다.

받는다면 과시용으로 자랑하며 허영심을 채우기 적당할 겁니다.