Google code jam 2019 Qualification Round 후기

구글 코드잼 2019년도 예선전 후기다. 간단하게 작성해보고자 한다.

 

방금 글 쓰다가 한번 날아가서 조금 대충쓰고 싶어졌다.

 

 

퀄리피케이션 라운드는 절대평가(30점)에다가 27시간동안이나 대회를 하므로 간단하게 풀어버리고

약속에 가려고 했으나, 현실은 약속시간 내내 3번째 문제 솔루션을 생각했다.

 

가볍게 첫번째 문제 Foregone Solution 문제를 보았다. 히든케이스 10^100를 커버하기 위해 익숙하지 않은

파이썬으로 해결했다.

 

모든 4를 3으로 바꾸어 버리는 식으로 코드를 짰다.

 

tc=int(input())

def solve(n):
    a=int(str(n).replace('4', '3'))
    b=n-a
    return str(a) + " " + str(b)
for t in range(1, tc+1):
    n=int(input())
    ans=solve(n)
    print ("Case #" + str(t) + ": " + ans)

 

두번째 문제 You can go your own way

 

대충 문제 읽어보니까 솔루션이 떠올랐는데, 너무 간단해서 함정이 있나 조금 생각했다. E와 S를 서로 바꾸어주면 간단히 해결된다.

요녀석은 빅인티저같은게 필요가 없어서 주력언어인 C++로 작성했다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tc;
    scanf("%d", &tc);
    for (int t=1; t<=tc; t++) {
        int n; scanf("%d", &n);
        string s;
        cin >> s;
        printf("Case #%d: ", t);
        for (size_t i=0; i < s.length(); i++) {
            if (s[i] == 'S') putchar('E');
            else putchar('S');
        }
        putchar('\n');
    }
	return 0;
}

 

 

세번째 문제, 욕심부리다가 엄청 오랫동안 생각했다.

간단하게 gcd를 구해서 하면 될 거라 생각했는데, 같은 숫자가 나오는 것을 간과했어서  WA를 엄청나게 뿜었다.

파이썬으로 제출한 것은 RE도 자주나왔다. 이유는 아직도 모르겠다..

 

원문이 AAA ABA 형식으로 나오게 되면, 인접한 cipher int value 가 동일한 값이 나오기 때문에 그냥 gcd를 구하면 1이 나오게 된다.

이 점을 유의해야 한다는 것을 까먹었다.

 

Runtime Error 때문에 C++로 솔루션을 작성해 보고, 후에 Python 으로 바꾸어서 히든케이스를 대비했다.

 

사용된 소수들은 인접 값이 다를때만 gcd로 죄다 구하면 되고, 해독할때는 소수 하나만 찾아내서 양옆으로 propagation 시키면 됬던 풀이이다.

 

일단 씨쁠쁠 풀이이다.

 

#include <bits/stdc++.h>
using namespace std;

int N, L;  
int plainValue[105];

int main() {
    int tc; cin >> tc;
    for (int t=1; t<=tc; t++) {
        memset(plainValue, 0, sizeof(plainValue));
        cin >> N >> L;
        vector<int> ciphers;
        set<int> primes;
        map<int, char> int2char;
        map<char, int> char2int;
        ciphers.clear();
        primes.clear();
        int2char.clear();
        char2int.clear();
        for (int i=0; i < L; i++) {
            int tmp; cin >> tmp;
            ciphers.push_back(tmp);
        }
        for (int i=0; i< L-1; i++) {
            if (ciphers[i] != ciphers[i+1]) {
                int cd = __gcd(ciphers[i], ciphers[i+1]);
                primes.insert(cd);
                primes.insert(ciphers[i]/cd);
                primes.insert(ciphers[i+1]/cd);
            }
        }
        char c = 'A';
        for (auto& p : primes) {
            if (int2char.find(p) == int2char.end()) {
                char2int[c] = p;
                int2char[p] = c++;
            }
        }
        
        int idx, pval, ppval;
        for (idx=0; idx < L-1; idx++) {
            if (ciphers[idx] != ciphers[idx+1]) {
                int cd = __gcd(ciphers[idx], ciphers[idx+1]);
                plainValue[idx+1] = cd;
                pval = ciphers[idx+1] / cd;
                ppval = ciphers[idx] / cd;
                break;
            }
        }
        
        
        for (int i=idx; i >= 1; i--) {
            plainValue[i] = ppval;
            ppval = ciphers[i-1] / ppval;
        }
        plainValue[0] = ppval;
        
        for (int i=idx+2; i < L; i++) {
            plainValue[i] = pval;
            pval = ciphers[i] / pval;
        }
        plainValue[L] = pval;
        
        printf("Case #%d: ", t);
        for (int i=0; i <= L; i++) {
            putchar(int2char[plainValue[i]]);
        }
        putchar('\n');
    }
}

 

이렇게 짠 녀석을 그대로 파이썬으로 옮기면 히든케이스도 커버할 수 있다.

 

def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x
    
def make_unique(l):
    t = []
    for v in l:
        if len(t)==0 or t[-1] != v:
            t.append(v)
    return t
   
tc=int(input())
for t in range(1, tc+1):
    plainValue = [0 for i in range(0, 110)]
    N, L = map(int, input().split(' '))
    ciphers = list(map(int, input().split(' ')))
    primes = []
    int2char = {}
    
    for i in range(0, L-1):
        if ciphers[i] != ciphers[i+1]:
            cd = gcd(ciphers[i], ciphers[i+1])
            primes.append(cd)
            primes.append(ciphers[i]//cd)
            primes.append(ciphers[i+1]//cd)
            
    primes.sort()
    primes = make_unique(primes)
    c = 'A'
    for p in primes:
        if int2char.get(p) == None:
            int2char[p] = c
            c = chr(ord(c) + 1)
            
    idx = 0
    pval = 0
    ppval = 0
    
    for idx in range(0, L-1):
        if ciphers[idx] != ciphers[idx+1]:
            cd = gcd(ciphers[idx], ciphers[idx+1])
            plainValue[idx+1] = cd
            pval = ciphers[idx+1] // cd
            ppval = ciphers[idx] // cd
            break
    
    for i in range(idx, 0, -1):
        plainValue[i] = ppval
        ppval = ciphers[i-1] // ppval
    plainValue[0] = ppval
    
    for i in range(idx+2, L):
        plainValue[i] = pval
        pval = ciphers[i]  // pval
    plainValue[L] = pval
    
    
    ans = ""
    for i in range(0, L+1):
        ans += int2char[plainValue[i]]
    print ("Case #" + str(t) + ": " + ans)

 

마지막 문제의 경우는 아직 풀지를 못했는데, 나중에 여유가 되면 한번 풀어보고 올려보도록 하겠다.