CodeJam 2019 Round 1A 풀이

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

A. Pylons

아이디어

B. Golf Gophers

아이디어

중국인의 나머지 정리를 이용해 풀이할 수 있다. 총 7번의 Try가 가능하기 때문에 18 이하의 소수 7개 (2, 3, 5, 7, 11, 13, 17)로 매 Try마다 Blade의 수를 통일하면 각 Try에서 방정식을 얻을 수 있다. 여기서 문제는 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510으로 10^6보다 작다는 것이다. 이 때 2나 3은 제곱하더라도 다른 소수와 서로소이기 때문에 널찍하게 (5, 7, 9, 11, 13, 16, 17)로 Blade를 통일하면 충분히 범위를 커버할 수 있다.

코드

import sys

def extended(a, b):
  a, b = max(a, b), min(a, b)
  r1, r2 = a, b
  s1, s2 = 1, 0
  t1, t2 = 0, 1

  while r2 > 0:
    q = r1 // r2
    r1, r2 = r2, r1 - q * r2
    s1, s2 = s2, s1 - q * s2
    t1, t2 = t2, t1 - q * t2
  return ((s1 + b) % b, (t1 + a) % a)

Primes = [5, 7, 9, 11, 13, 16, 17]
L = 5 * 7 * 9 * 11 * 13 * 16 * 17
T, N, M = input().split()
T, N, M = int(T), int(N), int(M)
for tt in range(1, T + 1):
  Ret = 0
  for prime in Primes:
    print (" ".join([str(prime)] * 18))
    sys.stdout.flush()

    response = sum([int(x) for x in input().split()]) % prime
    # x = response (mod prime)
    X = (L / prime) % prime
    a, b = extended(prime, X)
    Ret += (L / prime) * b * response

  print (str(int(Ret + L) % L))

C. Alien Rhyme

아이디어

최대 50개의 길이를 가지는 1000개의 단어에 대해서 추출가능한 접미사는 총 50000개다. 이 접미사를 최대로 매칭할 수 있는 경우를 찾으면 된다. 가장 간단한 방법은 일치하는 가장 긴 것부터 매치하는 방법이다. ZABCDE, BABCDE, ZCDE, CCDE의 단어가 있다고 하자. (ZABCDE, ZCDE)와 (BABCDE, CCDE)로 쌍을 지으면 CDE가 공통 접미사가 되기 때문에 한 쌍 밖에 만들 수 없다. (ZABCDE, BABCDE)와 (ZCDE, CCDE)로 쌍을 지으면 ABCDE와 CDE가 공통 접미사가 되기 때문에 두 쌍을 만들 수 있다.

즉, 긴 접미사부터 우선적으로 매칭을 시도하면 짧은 접미사에게 영향을 주지 않기 때문에 최대 매칭을 구할 수 있다.

코드

T = int(input())
for tt in range(1, T + 1):
  N = int(input())
  Words = []
  for i in range(N):
    Words.append(input())
  Suffixs = {}
  Dic = {}
  for i in range(N):
    for j in range(0, len(Words[i])):
      length = len(Words[i]) - j
      if length not in Suffixs:
        Suffixs[length] = []
      if Words[i][j:] not in Dic:
        Dic[Words[i][j:]] = []
      Suffixs[length].append(Words[i][j:])
      Dic[Words[i][j:]].append(i)
  Used = {}
  Ret = 0
  keys = list(Suffixs.keys())
  keys.sort(), keys.reverse()
  for key_ in keys:
    for word in Suffixs[key_]:
      # check suffix is already used
      if word in Used:
        continue
      # Filter out already used words
      for i in range(len(Dic[word]) - 1, -1, -1):
        if Dic[word][i] in Used:
          del Dic[word][i]
      # If pair can't be made, continue
      if len(Dic[word]) < 2:
        continue
      # Mark used index and word.
      Used[Dic[word][0]], Used[Dic[word][1]], Used[word] = True, True, True
      Ret += 2    
  print("Case #" + str(tt) + ": " + str(Ret))