CodeJam 2019 Qualification Round 풀이

◎ 이 포스트는 CodeJam 2019의 Qualification Round에 대한 설명과 풀이입니다. 자세한 문제 설명은 공식 사이트를 참조하세요. 아래 풀이는 개인적으로 작성한 것으로 CodeJam 공식 Analysis의 내용과 일치하지 않을 수 있습니다.

A . Foregone Solution

자릿수에 4가 없으면서 더해서 N이 되는 두 수 A, B를 찾는 문제다. 윗 자릿수부터 2로 나누어서 결과로 출력할 두 수에 담는다. 이 때 조건을 만족시키기 위해서 몇 가지 예외를 추가한다. 해당 자리가 7, 8, 9인 경우에 따라 각각 다르게 처리하는데 자릿수가 7인 경우는 399999와 같은 경우에서 마지막 자리를 나누는 과정에서 남는 홀수로 인한 올림으로 4가 나오는 것을 방지하기 위해 3, 3이 아니라 2, 5로 자리를 나눈다. 8이나 9인 경우에는 3과 5로 나누고 9에 대해서는 1을 그 다음자리로 넘겨준다. 일반적이지 않고 더럽게 짠 코드다.

T = int(input())
for tt in range(T):
    N = int(input())
    K = 10 ** (len(str(N)) - 1)
    A, B = "", ""
    while K > 0:
        Div = N // K
        if Div == 8 or Div == 9:
            A += '2'
            B += '6'
        elif Div == 7:
            A += '2'
            B += '5'
            N -= K
        else:
            A += str(Div // 2)
            B += str(Div // 2)
        N -= (Div // 2) * 2 * K
        K //= 10
    A, B = int(A), int(B)
    if N % 2 == 1:
      A += 1
    print ("Case #" + str(tt + 1) + ":", A, B)

B. You Can Go Your Own Way

경로가 상대편과 겹치지 않도록 시작점에서 도착지점까지 도달하는 경로를 출력하는 문제다. 그냥 상대방의 경로를 대각선 기준으로 대칭시키면 되기 때문에 S -> E, E -> S 치환으로 간단히 만들어낼 수 있다.

T = int(input())
for tt in range(T):
    N = int(input())
    Sequence = input()
    Ret = ""
    for c in Sequence:
      if c == 'S':
        Ret += 'E'
      else:
        Ret += 'S'
    print ("Case #" + str(tt + 1) + ":", Ret)

C. Cryptopangrams

평문이 존재하고 평문의 각 알파벳은 하나의 소수에 대응한다. 연속한 두 평문 글자에 대응하는 알파벳의 곱이 수열로 주어질 때 평문을 복원해내는 문제다. 연속한 두 원소의 GCD를 구하면 연속한 세 문자에서 중간의 문자를 알아낼 수 있다. 하지만 이게 항상 가능한 건 아닌데 a b a와 같이 평문이 주어지는 경우엔 두 암호문이 동일하기 때문이다. 따라서 GCD를 통해 나온 값이 무조건 소수라고 확신할 수 없다. 따라서 이 값들을 서로 나눠보면서 소수인지 검증하는 절차가 반드시 필요하다.

이 결과 또한 첫 번째 평문과 마지막 평문 문자열에 대응하는 값을 포함하지 않을 수도 있다. 이들 문자열은 인접한 암호문들과 공유되지 않기 때문이다. 따라서 이것은 암호문을 알려진 하나의 평문으로 나누어 얻어내야 한다. 서로 다른 인접한 암호문자열을 찾아낸 후에 이들의 GCD를 구하면 중간의 평문에 대응하는 소수를 알아낼 수 있다. 찾아낸 평문을 기준으로 왼쪽과 오른쪽으로 소수를 연속으로 나누어서 각 평문에 대응하는 모든 소수들을 밝혀낼 수 있다. 찾아낸 모든 소수를 오름차순으로 정렬해서 알파벳을 부여하면, 평문을 복원할 수 있다.

def FilterOutNotPrime(Arr):
    # Filter Out Prime
    Tmp = Arr[:]
    Tmp.sort()
    Primes = []
    for i in range(len(Tmp)):
        isPrime = True
        for j in range(i):
            if Tmp[i] % Tmp[j] == 0:
                isPrime = False
        if isPrime:
            Primes.append(Tmp[i])
    return Primes

def GCD(a, b):
    a, b = max(a, b), min(b, a)
    while a % b != 0:
      a %= b
      a, b = b, a
    return b

T = int(input())
for tt in range(T):
    N, Len = [int(x) for x in input().split()]
    Seq = [int(x) for x in input().split()]
    
    # Generate PrimeSet
    Mul = []
    for i in range(Len - 1):
        Mul.append(GCD(Seq[i % Len], Seq[(i + 1) % Len]))
    Primes = FilterOutNotPrime(list(set(Mul)))
    Primes.sort()

    # Fullfill PrimeSet
    primeSet = set()
    for i in range(Len):
      for p in Primes:
        if Seq[i] % p == 0 and Seq[i] != p:
          primeSet.add(p)
          primeSet.add(Seq[i] // p)
    primeSet = FilterOutNotPrime(list(primeSet))
    primeSet.sort()

    # Dics
    Dic, cnt = {}, 0
    for p in primeSet:
      Dic[p] = chr(65 + cnt)
      cnt += 1

    # Candidates
    i = 0
    while Seq[i] == Seq[i + 1]:
      i += 1

    # left
    c = GCD(Seq[i], Seq[i + 1])
    left = Dic[c]
    for j in range(i, -1, -1):
      c = Seq[j] // c
      if c in Dic:
        left = Dic[c] + left

    # right
    c = GCD(Seq[i], Seq[i + 1])
    right = ""
    for j in range(i + 1, Len):
      c = Seq[j] // c
      if c in Dic:
        right += Dic[c]

    print ("Case #" + str(tt + 1) + ": " + left + right)

D. Dat Bae

이 문제는 Small과 Large의 풀이 방식이 다르다. 물론 Large대로 Small을 풀 수 있다.

Small로 푸는 방식은 좀 직관적이다. 길이가 2^k라고 가정하면 2^(k-1) 길이를 갖는 연속한 0과 1을 붙여서 0000…1111의 문자열을 만든다. 이걸로 테스팅을 돌려서 나오는 0과 1의 갯수를 세면, 중앙을 기준으로 왼쪽과 오른쪽에 고장난 머신을 각각 분리해 낼 수 있다. 즉, 기존의 문제가 독립된 문제들로 분할된다. Small 케이스의 테스팅 횟수인 10번을 모두 사용하면 최대 1024개의 머신을 대상으로 1024개의 길이 1의 문제들로 쪼개진다. 최종 결과에서 문제가 있는 머신들만 고장남으로 표시하면 된다.

Large로 푸는 방식은 일반적으로 F = 5로 해결할 수 없지만, 문제 주어진 조건인 고장난 머신의 수 B가 최대 15개라는 제한 조건하에서 해결할 수 있다. 예를 들어서 N = 4이고 B = 2^0 이고 F = 1이라고 해보자. 0101로 테스팅을 하면 각 머신이 고장난 상태에 따라서 101,001,011,010의 별도의 상태를 얻는다. N = 16이고 B = 2^1이고 F = 2라고 해보자. 0011001100110011로 테스트하면 어떻게 결과가 나오더라도 문제가 발생한 구간(길이2)을 찾아낼 수 있다. 예를 들어 가장 앞의 두개가 문제라면 11001100110011이 될 것이고, 두 번째와 세 번째가 문제라면 01001100110011이 나올 것이다. 이후에 그 구간에 01을 집어넣으면 결과에서 그 구간에 해당하는 로봇중에서 뭐가 문제인지 알 수 있다.

N = 64이고 B = 2^2이고 F = 3이면 0000111100001111000011110000111100001111000011110000111100001111을 입력으로 넣어서 알아낼 수 있다. 이 경우에도 동일한 방법으로 해결할 수 있다.

아래는 Small에 대한 코드이다.

import sys

# Returns interval and diffs
def parseResponse(response, diffs, size):
    i = 0
    while i < len(response) and response[i] == '0':
        i += 1
    return [i, len(response) - i, size - i, diffs - size + i]
    
T = int(input())
for tt in range(1, T + 1):
    n, b, f = [int(x) for x in input().split()]
    intervals = [[2 ** f]]
    diffs = [[b]]
    depth = 0
    X, Y = 2 ** (f-1), 1
    for stage in range(f):
        atom = "0" * X + "1" * X
        guess = atom * Y
        
        # Guess        
        print (guess[:n])
        sys.stdout.flush()
        # Get Result
        response = input()
        adjustedResponse = response + guess[n:]
 
        # Parse Response
        idx = 0
        intervals.append([])
        diffs.append([])
        for i in range(len(intervals[depth])):
            interval = intervals[depth][i]
            diff = diffs[depth][i]
            left_size, right_size, left_diff, right_diff = parseResponse(adjustedResponse[idx:idx+interval], diff, X)
            intervals[depth + 1].append(left_size)
            intervals[depth + 1].append(right_size)
            diffs[depth + 1].append(left_diff)
            diffs[depth + 1].append(right_diff)
            idx += interval
        depth += 1       
        X //= 2
        Y *= 2
    ret = []
    for i in range(len(intervals[depth])):
      if intervals[depth][i] == 0:
        ret.append(str(i))
    if len(ret) == 0:
      print ("0 " * b)
    else:
      print (" ".join(ret))
    sys.stdout.flush()
    verdict = input()