Loading [MathJax]/jax/output/HTML-CSS/jax.js
본문 바로가기

Computer Science/Competition

Google Code Jam Round 1C

어제 참여한 Google Code Jam Round 1C에서 68점(패널티 1:27:23)으로 전체 355등을 하며 Round2에 진출하게 되었다. Round2는 약 2주 후에 개최된다. (문제/스코어보드 링크)

 

문제 풀이

A. Overexcited Fan

시각 t에 Peppurr의 위치를 r(t)=(x(t),y(t))라 하자. 이 때, 시각 t에 Peppurr를 만날 수 있을 필요충분조건은 dist(O,r(t))=|x(t)|+|y(t)|t가 됨을 확인할 수 있다. (단, O는 원점)

 

따라서, 각 1tlen(M)에 대해 이 부분을 확인해주면 문제를 해결할 수 있다. 시간 복잡도는 총 O(len(M))이다.

B. Overrandomized

먼저, 0에 대응되는 문자 부터 찾자. 0은 수의 맨 앞자리에 올 수 없으므로, 등장한 모든 문자들 가운데 맨 앞에 등장한적이 없는 문자가 0에 대응된다.

 

이제, 나머지 숫자들을 결정해주면 된다. 여기에서 핵심이 되는 관찰은 작은 수일 수록 등장할 확률이 높다는 것이다. 보다 엄밀하게는 N=10U라 할 때,

Pr(Ri=X)=Nk=XPr(Ri=X|Qi=k)Pr(Qi=k)=Nk=X1k1N=1N(1X+1X+1++1N)1N(logNlogX)

가 됨을 lognnk=11k 라는 사실로 부터 알 수 있다.

 

따라서, 맨 앞에 등장한 횟수가 큰 문자부터 순서대로 1,2,,9에 대응된다.

 

import sys

inp = lambda : sys.stdin.readline().strip()

T = int(inp())
for t in range(T):
    print ("Case #" + str(t+1) + ": ", end='')
    U = int(inp())
    S = set()
    F = set()
    cnt = dict()
    for _ in range(10000):
        q, r = inp().split()
        q = int(q)
        F.add(r[0])
        if r[0] not in cnt: cnt[r[0]] = 1
        else: cnt[r[0]] += 1
        S |= set(list(r))
    df = S - F
    res = [df.pop()]
    L = [ (cnt[key], key) for key in cnt ]
    L.sort()
    L.reverse()
    for val, key in L: res.append(key)
    print (''.join(res))

C. Oversized Pancake Chopper

이 문제의 경우 Test Set 1만 해결해도 Round 2에 진출할 수 있는 상황이라 굳이 Test Set 2, 3을 풀지는 않았다. Test Set 1과 2에 대한 풀이만 적어두도록 하겠다.

Test Set 1

D=2 혹은 D=3인 경우에 대해서만 해결하면 된다. D=2인 경우, 크기가 같은 두 조각이 있으면 0, 아니면 1이 답이 된다.

 

D=3인 경우는 조금 더 까다롭다.

  • 크기가 같은 세 조각이 있으면 0,
  • 크기가 같은 두 개의 조각만 있거나, 혹은 한 조각의 크기가 다른 조각의 두 배가 되는 쌍의 조각이 있으면 1,
  • 아니면 2가 답이다.

Test Set 2

일단, 최악의 경우, 하나의 조각을 D등분 하게 되므로 답이 D1이라는 점을 먼저 짚어두자.

 

어느 조각에서 잘려져 나온 모든 결과물을 serve 하게 된다면, 그 조각을 좋은 조각이라고 하자. 손님들에게 팬케이크를 나눠주는 과정에서 좋은 조각이 X개 있다면, 문제의 답은 DX이다. 즉, 앞에서 말해둔 최악의 경우는 X=1인 경우라고 할 수 있다.

 

이 관찰에 의해 각 손님이 받게 되는 팬케이크의 크기는 N/K (단, K=1,2,,D)가 된다. 손님이 받는 팬케이크의 크기를 고정하면, 최소 칼질 횟수는 O(N)에 구할 수 있다. 손님이 받는 팬케이크의 크기는 총 O(ND)가지 경우가 있으므로, 총 시간 복잡도 O(N2D)에 이 문제를 해결할 수 있다.