Google Kick Start 2018 - Round H
Goolge Kick Start가 열린다는 메일을 받고 부랴부랴 기출문제를 풀어보았다. Kick Start는 간단히 말해서 Code Jam 보다 쉬운 대회로, “구글에서 일하기 위해 필요한 기술들을 맛볼 수 있는” 대회라고 한다.
The three-hour rounds feature a variety of algorithmic challenges, all developed by Google engineers so that you get a taste of the technical skills needed for a career at Google.
오늘 소개할 문제들은 Kick Start 2018 Round H의 문제들이다.
Big Buttons
R과 B로 길이가 N인 문자열을 만들 때, 주어진 p개의 prefix 중 어느 것과도 겹치지 않는 prefix로 시작하는 문자열의 개수를 구하는 문제이다.
풀이는 간단하게 주어진 prefix 로 Trie를 만들고, 루트부터 탐색해서 링크가 끊어지는 부분을 찾아서 개수를 세면 된다. 사용 가능한 문자가 R과 B 뿐이므로 개수는 쉽게 셀 수 있다. ($2^n$ 꼴)
class Trie:
def __init__(self):
self.link = {}
self.end = False
def add(self, s):
c, i = self, 0
while i < len(s):
nc = s[i]
if nc not in c.link:
c.link[nc] = Trie()
c = c.link[nc]
i += 1
c.end = True
def count_feasible(self, n):
if self.end or n <= 0: return 0
ret = 0
for x in ['R', 'B']:
if x not in self.link:
ret += 1 << (n - 1)
continue
ret += self.link[x].count_feasible(n - 1)
return ret
def solve(n, ss):
trie = Trie()
for s in ss: trie.add(s)
return trie.count_feasible(n)
T = int(input().strip())
for C in range(1, T + 1):
n, p = map(int, input().split())
ss = [input().strip() for _ in range(p)]
print("Case #{}: {}".format(C, solve(n, ss)))
Mural
일렬로 서 있는 n개의 벽에 그림을 그리려 한다. 처음 그림을 그릴 벽은 마음대로 선택할 수 있고, 이후에는 먼저 그림을 그린 벽과 인접한 벽에만 그릴 수 있다.
그림을 하나 그릴 때마다 그림과 인접하지 않은 끝 벽이 한 개씩 무너져내린다고 할 때, 벽이 어떻게 무너지든 상관 없이 확실히 얻을 수 있는 최대의 아름다움을 계산해보자. (아름다움은 그림이 그려진 벽의 점수 (*문자열로 주어진다) 의 합이다)
그냥 보면 왼쪽 벽이 무너질지 오른쪽 벽이 무너질지 고민이 되지만, 사실 연속된 (n+1) / 2 개의 벽은 모두 선택해볼 수 있다:
그림이 그려진 벽과 인접한 벽 또한 무너지지 않기 때문에, 실제로 무너지기 전에 그림을 그려야 할 벽은 (n+1) / 2 - 2 개가 된다 (양 끝에 인접한 벽에는 가장 마지막에 그리면 되므로). 이러한 조건을 고려하면, 무조건 ‘중간 벽’부터 선택할 경우 예외 없이 항상 그릴 수 있는 것을 확인할 수 있다.
따라서 partial sum 을 구해두고, 가능한 (n+1) / 2 개의 연속된 벽의 아름다움 중 가장 큰 것을 구하면 끝!
def solve(n, s):
ans = 0
d = [0] * (n + 1)
for i in range(1, n + 1): d[i] = d[i-1] + int(s[i])
for i in range(0, n // 2 + 1):
ans = max(ans, d[i + (n+1) // 2] - d[i])
return ans
T = int(input().strip())
for C in range(1, T + 1):
n = int(input().strip())
print("Case #{}: {}".format(C, solve(n, '0' + input().strip())))
Let Me Count The Ways
n 쌍의 커플을 아주 긴 배에 일렬로 태우려 한다. 이중 m 쌍의 신혼 커플은 서로 인접한 자리에 태우지 않는 경우의 수를 구해보자.
Inclusion-Exclusion (포함-배제) 원리 ($|A\cup B| = |A| + |B| - |A\cap B|$) 로 해결할 수 있다. 원래 이런 방법을 이용할 때에는 모든 집합을 살펴보기 때문에 $2^n$ 의 복잡도를 갖지만, 여기서는 각 집합의 크기가 동일하므로 $O(m)$ 개의 집합만 살펴보면 해결할 수 있다.
귀찮은 점으로는, n 과 m 이 큰 경우가 있어서 큰 수 모듈러 계산을 해야한다는 것이 있다.
from functools import lru_cache
factorials = [1]
MOD = 1000000007
def factorial(n):
while len(factorials) <= n:
factorials.append(factorials[-1] * len(factorials) % MOD)
return factorials[n]
@lru_cache(maxsize=None)
def modpow(n, m):
ret = 1
while m > 0:
if m & 1 > 0:
ret = ret * n % MOD
n = n * n % MOD
m >>= 1
return ret
@lru_cache(maxsize=None)
def factorial_inverse(n):
return modpow(factorial(n), MOD - 2)
def binomial(n, k):
return factorial(n) *\
factorial_inverse(k) % MOD *\
factorial_inverse(n - k) % MOD
def solve(n, m):
ans = factorial(n * 2)
for k in range(1, m + 1):
sign = -2 * int(k % 2 > 0) + 1
val = binomial(m, k) *\
binomial(2 * n - k, k) % MOD *\
factorial(k) % MOD *\
factorial(2 * (n - k)) % MOD *\
modpow(2, k) % MOD
ans += sign * val
return (ans % MOD + MOD) % MOD
T = int(input().strip())
for C in range(1, T + 1):
n, m = map(int, input().split())
print("Case #{}: {}".format(C, solve(n, m)))