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의 문제들이다.

  1. Big Buttons
  2. Mural
  3. Let Me Count The Ways

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)))