Google Code Jam 2019 Qualification Round
이번 GCJ 퀄 라운드는 간단한 아이디어로 풀리는 문제가 많아서 재미있었다. 물론 C번은 런타임 에러가 발생할 수 있는 함정이 여럿 있었고, 큰 수 나눗셈 계산이 필요해서 언어 선택에 조금의 제한이 생기기는 했지만.
Foregone Solution
4가 한 개 이상 포함된 숫자 N을, 4를 포함하지 않는 두 양의 정수 X와 Y의 합으로 나타내는 문제,
즉 str(X).count('4') == 0 and str(Y).count('4') == 0 and X + Y == N인 X, Y를 아무거나 찾으면 된다.
따라서 풀이는 그냥 4가 나타나는 자리에만 2가 들어가도록 하면 끝!
T = int(input().strip()) + 1
for C in range(1, T):
x = input().strip()
a = x.replace('4', '2')
x = int(x) - int(a)
print("Case #{}: {} {}".format(C, x, a))You Can Go Your Own Way
N by N 격자에서 오른쪽과 아래 쪽의 이동만 이용해서 왼쪽 위의 점부터 오른쪽 아래 점으로 이동하는 경로를 출력하는 문제이다. 다만, 하나의 경로가 주어지고, 이 경로와 겹치는 이동이 있어서는 안 된다. 이 문제의 풀이 역시도 정말 간단한데, 두 개의 이동 방법으로 끝 점까지 이동하기 위해서는 N-1 번의 아래 이동과 N-1번의 오른쪽 이동이 필요하다는 것을 이용해서, 주어진 이동 경로의 오른쪽과 아래 이동을 서로 바꾸면 항상 90도 회전한 경로로 이동하므로 겹치지 않고 이동할 수 있다.
T = int(input().strip()) + 1
for C in range(1, T):
_, x = input(), input().strip()
a = x.replace('E','s').replace('S','E').replace('s','S')
print("Case #{}: {}".format(C, a))Cryptopangrams
N 이하의 소수 중에서 26개를 뽑아 크기 순서대로 각 소수에 A, B, …, Z 를 대응시켰을 때, 알파벳 대문자로 이루어진 팬그램 (모든 알파벳이 한 번 이상 등장하는 문자열) 을 연속된 두 문자에 대응하는 소수의 곱으로 암호화 한 결과가 주어진다. N과 암호화된 정수의 리스트를 가지고 복호화 하는 문제이다.
팬그램이기 때문에 풀이는 매우매우 간단하게 떠오르지만, 이번 라운드에서 가장 많은 함정을 가지고 있는 문제가 아니었을까 싶다.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
6 15 35 77 143 221 323 437 667 899 1147 1517 1763 2021 2491 3127 3599 4087 4757 5183 5767 6557 7387 8633 9797
첫 문자와 마지막 문자를 제외한 모든 문자는 암호문에서 두 번 등장하는 사실을 알 수 있다. 예를 들어 B는 6과 15에 모두 등장하므로, gcd(6, 15) 를 이용해 소수가 3과 대응되는 알파벳이 있음을 알 수 있다.
같은 방법을 반복하면 3, 5, 7, …, 97 총 24개의 소수를 찾을 수 있다.
나머지 두 소수 역시 6을 3으로 나누고, 9797을 97로 나누면 2와 101임을 알 수 있다.
이제 이렇게 얻은 소수에 크기 순서대로 A, B, …, Z 를 대응시키면 끝!
함정: 팰린드롬
A와 B를 너무 쉽게 풀어서, 이것도 간단하겠지~ 하면서 막 내다가, 부끄럽게도.. 결국 테스트 데이터 생성기를 짜고 나서야 이 함정을 깨달았다.
ABACDEFGHIJKLMNOPQRSTUVWXYZ
6 6 10 35 77 143 221 323 437 667 899 1147 1517 1763 2021 2491 3127 3599 4087 4757 5183 5767 6557 7387 8633 9797
실제로는 이렇게 암호문에 같은 수가 등장하는 경우도 고려해주어야 한다. (ABA => 6 6)
아까처럼 무작정 gcd를 구해서 끝내면 소수가 아닌 6이 들어가고 2는 찾지 못할 수 있으니 주의.
사실 n이 작으니까 적당히 2중 루프로 모든 경우를 구해보는 것도 좋은 방법이다. (아래 코드)
from fractions import gcd
from string import ascii_uppercase
def uniq(x): return sorted(list(set(filter(lambda y: y != 1, x))))
alphabet = [x for x in ascii_uppercase]
def decrypt(d, c, s):
a = [s]
for i in range(n-1): a.append(c[i] // a[-1])
return "".join([d[u] for u in (a + [c[-1] // a[-1]])])
T = int(input().strip()) + 1
for C in range(1, T):
_, n = map(lambda x: int(x.strip()), input().split())
x = list(map(lambda x: int(x.strip()), input().split()))
g = uniq(sum([[gcd(a, b) for b in x if gcd(a, b) > 1 and a != b] for a in x], []))
g = uniq(sum([[a // b for b in g if a % b == 0] for a in x], g))
d = {p: q for q, p in zip(alphabet, g)}
for p in filter(lambda p: x[0] % p == 0, g):
try:
print("Case #{}: {}".format(C, decrypt(d, x, p)))
break
except: passDat Bae
1과 0으로 이루어진 길이 N의 메시지를 보내면 각 컴퓨터가 차례로 자신이 받은 값을 그대로 응답으로 돌려주는 시스템이 있다. 다만 N 대의 컴퓨터 중 B 대가 고장나서 응답을 주지 않는 상태일 때(즉 요청의 길이는 N이지만 응답의 길이는 N - B이다), 최대 F번의 쿼리를 이용해 고장난 B개 컴퓨터의 번호를 찾는 문제이다.
정해와는 조금 다르게, BFS와 비슷한 방법으로 해결했다. 간단하게 스몰(Test Set 1) 문제를 다음과 같은 트리 형태로 나타내어 보자. ([구간 시작, 구간 끝], 구간 내 고장난 머신의 개수)
노드의 개수가 최대 1024개이므로 트리의 높이는 10이 되고,
각 높이 별로 쿼리를 한 번씩 하면 어느 칸이 고장인지 간단히 알 수 있다.
각각의 노드에서 구간을 두 개로 쪼갤 때,
왼쪽 절반에는 1, 오른쪽 절반에는 0을 부여하면
위의 그림처럼 쿼리 결과의 1과 0의 개수를 세어 각 구간에 고장난 머신이 몇 개 존재하는지 알 수 있다.
이를 구간 별로 따로 진행하면 쿼리가 많이 필요하지만, 같은 레벨 (높이) 에 있는 구간을 모아서 처리하면 트리의 높이 만큼, 즉 최대 10번의 쿼리만 이용해서 모든 구간의 고장난 노드의 수를 얻을 수 있다.
Test Set 2 (F = 5) 일 때에는 어떻게 하면 될까?
기존과 같이 트리의 각 레벨 별로 한 번씩 쿼리를 하되,
가능할 경우 구간을 2개보다 잘게 나누어서 높이를 줄이면 된다.
중요한 아이디어는, 구간을 쪼갰을 때 아무리 많이 고장나도 구간 하나가 통째로 지워지지 않을 만큼만 쪼개면 ((length - 1) // broken) 앞서 살펴본, 구간을 2개로 나누는 방법과 거의 똑같이 처리할 수 있다는 것이다.
이렇게 접근했을 때 최악의 경우는 무엇일까?
결국 트리의 높이가 최대한 높아지는 것이 최악인데,
예를 들면 n = 1024, b = 9 ([2, 4, 8, 16, 32, 64, 128, 256, 512]) 가 있다.
그리고 직접 과정을 진행해 보면, 이러한 경우에도 쿼리 5번에 모든 고장난 노드를 찾을 수 있음을 확인 가능하다.
(각 쿼리별로 발견하는 노드: [] -> [32, 64, 128, 256] -> [16, 512] -> [2, 4] -> [8])
from sys import stdout
def send(q):
print("".join([str(x) for x in q]), flush=True)
res = input().strip()
if len(res) == 2 and res == "-1": exit(-1)
return res
def query(length, ranges):
data = [0] * length
for pos, length, bit, _, used in ranges:
if used: continue
for k in range(length):
data[k + pos] = bit
return send(data)
def divide_range(pos, length, bit, broken, used):
if broken == 0 or length == 0:
return [], []
if broken == length:
return [] if used else [pos + x for x in range(length)], [[pos, length, bit, broken, True]]
k = max(2, (length-1) // broken)
m = length // k
nxt = [[pos + m * j, m, (j+1) % 2, 0, False] for j in range(k-1)]
nxt += [[pos + m*(k-1), length - m*(k-1), k % 2, 0, False]]
return [], nxt
def clean(result, bit):
return result[:result.rfind(str(1 - bit))] if len(result) > 0 and int(result[-1]) != bit else result
def solve(n, broken, f, pos=0):
q, ans, query_count = [[pos, n, 0, broken, False]], [], 0
while len(q) > 0 and query_count <= f:
ranges = [divide_range(*rng) for rng in q]
ans = sum([rng[0] for rng in ranges], ans)
q_next = sum([rng[1] for rng in ranges], [])
if len(q_next) == 0 or query_count >= f: break
query_res, query_count = query(n, q_next), query_count + 1
faults, nptr = 0, 0
for i in range(len(q)):
pos, length, bit, broken, _ = q[i]
if broken == length or broken == 0:
nptr, faults = nptr + int(broken > 0), faults + broken
continue
k = max(2, (length-1) // broken)
m = length // k
actual_pos, actual_length = pos - faults, length - broken
result = query_res[actual_pos:actual_pos + actual_length]
pos = 0
for j in range(k):
length = q_next[nptr][1]
current = clean(result[pos:pos+length], (j + 1) % 2)
faults_found = length - sum([(j + 1) % 2 == int(x) for x in current])
q_next[nptr][-2] = faults_found
pos, faults, nptr = pos + length - faults_found, faults + faults_found, nptr + 1
q = q_next
return " ".join([str(x) for x in sorted(ans)])
T = int(input().strip())
for C in range(1, T + 1):
n, b, f = map(lambda x: int(x.strip()), input().split())
w = solve(n, b, f)
print(w, flush=True)
if int(input().strip()) == -1: exit(-2)
exit(0)사실 이건 문제의 난이도 보다는 인터랙티브 문제라 테스트가 매끄럽지 않아서 힘들었다.