Code jam 2016 quals round (D, Fractiles)

문제 링크 : https://code.google.com/codejam/contest/6254486/dashboard#s=p3

문제

이번껀 줄이기 귀찮아서 그냥 통짜로 옮겨 놓는다.

오랜 옛날, 어떤 프랙탈 부족이 타일을 쭉 늘어놓는 예술 작품을 만들며 살아왔다. 그 프랙탈 부족은 두 가지의 타일을 사용했는데, 하나는 금(G)이고 하나는 납(L)이었다.

각 프랙탈 예술 작품은 최초 타일 갯수 K,와 복잡도 C의 두가지 변수로 나타낼 수 있다. 일단 주어진 최초 타일들에 대해서, 최초 타일열 작품 그 자체는 복잡도 1을 가진다. 그리고 복잡도 X+1의 작품은 복잡도 X의 작품을 다음과 같은 규칙으로 변형 해서 만들 수 있는데,

1. 복잡도 X 작품에서 모든 L타일은 그 복잡도 X 작품 자체로 치환된다.
2. 복잡도 X 작품에서 모든 G타일은 K개의 G타일로 치환된다.

예를 들어, 최초 타일열이 LGL 이고, 복잡도 1에서부터 3까지는 각각 다음과 같을것이다.

• 복잡도 1 : LGL
• 복잡도 2 : LGL GGG LGL (공백은 보기 좋으라고 내 맘대로 넣은겁니다. 없다고 생각하면 됨)
• 복잡도 3 : LGLGGGLGL GGG GGG GGG LGLGGGLGL

아래는 복잡도 1 타일 작품으로부터 복잡도 2 작품이 어떻게 나오는지 보여주는 그림이다.

그림1. LGL예제

당신이 방금 프랙탈 부족의 작품을 하나 발견했다고 하자. 하지만 수학문제가 다들 그렇듯 오랜 세월에 더러워져서 이게 금인지 납인지 겉으로 봐선 모를지경이 되어버렸다. 그렇지만 놀랍게도 당신이 왠지 고고학자 교수라 이런 프랙탈 문화에 조예가 깊어서 K와 C값을 알고 있다고 쳐보자. 물론 최초 타일 배열이 어떻게 생겨먹었는진 모르지만 당신은 타일들 중에 금으로 만들어진게 있는지 알아보고자 한다. 당신이 S명의 불쌍한 대학원생을 고용해서 한 사람당 한 타일씩 닦아보게 시킬 수 있다면, 과연 당신은 금 타일을 발견할 수 있을까? 만약에 발견 할 수 있다면, 어딜 닦아봐야 할까? (타일열 인덱스는 1부터 시작한다)

과도한 오역이 남용되었으니 뭔 말인지 모르겠으면 원본 링크를 참조하자.

입력

테스트 케이스(T)당 K, C, S가 주어진다.

이때,
1 <= T <= 100.
1 <= K <= 100.
1 <= C <= 100.
K * C <= 1018.

출력

각 테스트 케이스마다 ‘Case #x: y’ 꼴로 출력한다. 이때 x는 (1부터 시작하는) 테스트 케이스 번호, y는 해답. 답이 없으면 ‘IMPOSSIBLE’을 출력한다.

내 풀이

개인적으로 양 숫자 세는 문제랑 팬케이크 뒤집기 문제보단 약간 머리를 조금 더 써야하고, 코인잼 문제보단 쉽고 빠르게 풀 수 있다고 생각한다.

첫번째 LGL예제를 다시 생각해보자. 이 글에는 복붙하진 않았지만 구글이 제시한 저 예시에 대한 답은 마지막 테스트 케이스 (K = 3, C = 2, S = 3)에서 볼 수 있듯 2 6이다. 두번째 타일과 여섯번째 타일만 닦아 본다면 세명분의 월급을 안 주더라도 최초 타일에 골-든 타일이 있는지 없는지 알 수 있다는 이야기다. 그럼 여기서 두번째 타일이랑 여섯번째는 왜 다른 타일보다 뭐가 다르길래 답이냐?

그림 2. LGL예제 (C=2)

복잡도를 한번 올려보면서 어떤식으로 골드 타일이 퍼져 나가는지 생각해보자. 일단 최종 결과물인 두번째 복잡도(C=2) 타일들중 가장 왼쪽 타일(파란색 1번)이 골드 타일이 되려면, 그 전 세대인 첫번째 복잡도(C=1) 타일인 1, 2, 3이 각각 뭐가 되어야 할까? 규칙을 다시 생각해보자. 파란색 맨 앞 세개(K개) 타일들은 검정색 1번만이 어떤 타일이냐에 따라 운명이 갈린다. 검정색 2,3번은 파란색 1,2,3번의 운명에 아무 역할도 주지 못한다. 이 시점에서 만약 검정색 1번이 G 타일이면, 파란색 1, 2, 3 번은 전부 원본 타일열과 상관없이 그냥 G가 된다. 하지만 만약에 검정색 1번이 L타일이면 규칙에 따라 파란색 1,2,3 번은 각각 검정색 1,2,3 번과 똑같은 종류를 따라가게되고, 그건 파란색 1번에게는 무조건 L이 된다. 파란색1이 G가 되려면 검정색 1번이 G여야 한다는 첫번째 조건을 알아냈다. 마찬가지로 파란색 2번이 G가 되려면 검정색 타일들이 뭐가 되어야 할까? 파란색 2번 입장에서는 검정색 1번이 G이기만 해주면 파란색 1,2,3번이 싸그리 G가 되기 때문에 이 경우에도 G가 된다. 그리고 또, 검정색 1번이 L이더라도 어차피 파란색 2번은 검정색 2번의 타입을 물려받게 되므로 검정색 2번 타일만 G타일이면 된다. 다시 정리하자면 파란색2가 G가 되려면 검정색 1번이 G거나, 아니면 검정색 2번이 G이면 된다. 얘네들을 한번에 모아서 보면 아래와 같다.

1. 파란색 1번 = 검정색 1번;
2. 파란색 2번 = 검정색 1번 || 검정색 2번;
3. 파란색 3번 = 검정색 1번 || 검정색 3번;
4. 파란색 4번 = 검정색 2번 || 검정색 1번;
5. 파란색 5번 = 검정색 2번;
6. 파란색 6번 = 검정색 2번 || 검정색 3번;
7. 파란색 7번 = 검정색 3번 || 검정색 1번;
8. 파란색 8번 = 검정색 3번 || 검정색 2번;
9. 파란색 9번 = 검정색 3번;

여기서 타일들의 가치가 달라지게 된다. 첫번째 파란색 타일을 닦아 본다면 검정색 타일 1번만이 G였는지 아닌지만 확인 해보게 되는 꼴이 되는데, 두번째 파란색 타일을 닦는다면 검정색 1번, 2번이 G였는지 아니었는지 동시에 확인하는게 된다. 문제가 ‘적어도 하나의 골드 타일이 있는지를 최소한의 노동력으로 알아보라’는 것 이었으니, 당연히 한번에 많은 정보를 담고 있는 타일을 닦는게 훨씬 낫겠지. (참고로 여기서 2 9도 마찬가지로 정답이다. 파란색 2번이 검정색 1,2번, 파란색 9번이 검정색 3번에 대한 정보를 가지고 있을테니)

물론 한 타일에 모든 최초 타일 정보가 쫘르륵 들어가 있어서 걔만 닦아보면 편하겠지만, 위에 규칙들만 봐도 알겠지만 한 타일에 들어갈 수 있는 최대 정보는 해당 타일열의 복잡도(C)까지가 최대다. 왜냐면 타일이 다음 복잡도로 넘어갈때 영향을 받는 원본 타일의 갯수가 최대 두개밖에 안되니…

위의 배경지식을 가지고 문제를 (귀찮겠지만) 다시 생각해 보자. 1,2…,K 에 대한 정보를 가질 수 있는 C 복잡도의 타일들을 최대 S명을 이용해서 알아봐야 한다. 또 다시 LGL 문제를 풀어보자면, 최종적으로 복잡도 C가 2니까 한 타일당 가질 수 있는 최대 정보의 갯수는 2개다. 알아 내야할 원본 타일들은 K가 3이니까 1,2,3이고. 그럼 이렇게 해보자. 1,2번 정보를 가지고 있는 타일이랑 3번 정보를 가지고 있는 타일을 까보면 되겠다. 그럼 되겠지? 또 다시 예를 들어서 (K=4, C=3, S=2)인 문제를 풀어보자. 최종 복잡도에서는 C가 3이라 한 타일당 세개의 정보를 담고 있을테니 1, 2, 3번 정보를 가지고 있는 타일 까보고 마지막으로 4번 정보를 가지고 있는 타일 을 까면 된다.

그림 2. LGL예제 일부 (C=3)

그럼 특정 정보들을 가지고 있는 타일들의 위치를 어떻게 알아낼지를 생각보자. 파란색 1,2,3번(K개)은 공통적으로 검정색 1번에 대한 정보를 가지게 된다. 왜냐면 검정색 1번에 따라서 아예 골-든 타일열이 되거나, 원본 타일열을 고대로 가져오거나 하니까. 마찬가지로 두번째 그룹 4,5,6 번은 공통적으로 검정색 2번에 대한 정보를 가지고 있게 된다. 검정색 2번에서부터 파생될테니. 파란색 7,8,9도 역시 검정색 3번에 대한 정보를 가지고 있게 되고. 여기서 복잡도를 하나 더 늘려서 생각해보자. 빨간색 4,5,6은 보다시피 파란색 2번으로부터 파생된 타일들이다. 따라서 파란색 2번이 검정색 1번과 2번에 대한 정보를 가지고 있었던것에 더해, 빨간색 4,5,6은 각각 검정색 (1,2,1) / (1,2,2) / (1,2,3) 에 대한 정보를 가지고 있게 된다. 좀 더 일반화 하자면, 각 복잡도의 타일을 K개씩 그룹으로 나눴을때 ‘몇 번째 그룹’에 해당하느냐에 따라 그 그룹-번째에 대한 정보를 가지고 있게 된다. (그 그룹-번째 타일로부터 파생된거니까) 예를들어 빨간색 6번은 복잡도가 1인 타일에선 첫번째 그룹이었고, 복잡도가 2인 타일에선 두번째 그룹이었고, 복잡도가 3인 타일에선 세번째 타일이니까 1,2,3번이 G인지 아닌지에 대한 정보를 가지고 있다. (= 셋 중에 하나라도 G면 빨간색 6번이 G타일이다) 요렇게 쉽게 인덱스만 타고 들어가면 위치를 구할 수 있다. 끝.

코드

그래서 코드는 다음과 같..은데 실제로 이 코드를 제출한건 아니고 사실 그때 짠 소스를 한번 이쁘게 고친 버전이다. 네이밍도 사실 앞에 팬케이크 뒤집는 문제에 비하면 딱히 직관적이진 않지만 그래도 나름 보다보면 봐줄만 하다.

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

#include <cmath>
#include <cstdint>

using namespace std;

typedef uint64_t u64;

int main() {
    int count;
    cin >> count;

    for (int i = 1; i <= count; i++) {

        // K : number of initial tiles
        // C : final complexity
        // S : number of graduate students available

        int K, C, S;
        cin >> K >> C >> S;

        // Each tile can have C infos max, you can clean S tiles max.
        // if you have to find more then that, thas's impossible
        if (C * S < K) {
            cout << "Case #" << i << ": IMPOSSIBLE" << endl;
            continue;
        }

        // output tile index set
        set<u64> output;

        // loop of indices 
        // 1st loop : (1, 2) 2nd loop : (3)
        for (u64 j = 1; j <= K; j += C) {

            // begin, end of tile indices
            u64 begin = j;
            u64 end = min(begin + C - 1, (u64)K); // you can't check index exceeding K

            // build propositional disjunction expression
            vector<u64> groups(C);

            for (u64 l = 0; l < C; l++) {
                groups[l] = min(begin + l, end);
            }

            // find tile index has infos about that indices
            u64 ans = begin;
            vector<u64>::iterator it = groups.begin();
            for (int l = 1; l < C; l++) {
                ++it;
                ans = ans - 1;
                ans = ans * K;
                ans = ans + (*it);
            }

            output.insert(ans);
        }

        // you need too many of graduate students
        if (output.size() > S) {
            cout << "Case #" << i << ": IMPOSSIBLE" << endl;
            continue;
        }

        // print
        cout << "Case #" << i << ":";

        for (u64 e : output) {
            cout << " " << e;
        }

        cout << endl;
    }

    return 0;
}

그래서

이번껀 설명이 꽤나 장황한데, 이 문제를 풀면서 해답을 생각했던 방식 그대로 옮겨 적다보니 그런듯. 사실 구글 공식 해설은 따로 보진 않았다.

이 날은 요렇게 코드잼 풀이를 마무리 했었고 C번 Large set을 못 풀어서 20점 감점으로 총 80점으로 마무리 했었다. 하지만 정작 퀄리피케이션 라운드만 통과하고 본 예선부터는 일하느라 못했음. -_-

암튼 당시에 회사에서 하던 일반적인 로직 프로그래밍과는 아예 다른 알고리즘 프로그래밍을 오랜만에 모여서 풀어보니 재밌었다. 정작 각자 이야긴 안 하고 따로 풀었지만... 좀 더 이런 기회가 앞으로 많이 있었으면.