ls-al.me hello, world!

Facebook Hacker Cup 2017 R1

35점 이상을 획득하면 R2에 진출할 수 있다.

10: Pie Progress

일동안 가게에서 개의 파이를 판매한다. 매일 이 판매하는 파이들의 부분집합을 구매해서 일동안 총 개의 파이를 구매하는 최소 비용을 구해야 한다. 단 파이의 가격은 매일 달라지며 하루에 개의 파이를 구매하면 파이의 가격에 추가로 의 세금이 발생한다.

가장 쉬운 방법은 각 날마다 가게에서 판매하는 파이를 저렴한 순으로 정렬한 뒤 하나씩 구매할 때 발생하는 세금의 차액까지 파이의 가격에 추가하는 것이다. 예를 들어 3개의 파이를 판매한다면 가장 저렴한 파이에는 1, 그 다음 파이에는 3, 그 다음 파이에는 5의 가격을 추가한다. 이 상태에서 모든 날에 판매하는 파이들 중 가장 저렴한 개의 파이를 선택하면 된다.

하지만 대회중에는 간단한 방법을 생각해 내지 못하고 DP로 접근했는데, 일까지 개의 파이를 구매하는 최소 비용으로 정의하면 에 해결 가능하다. 하지만 제출 과정에서 dictionary로 구현한 코드의 버그를 발견했고 이를 남은 시간동안 제출하기 위해 list를 사용하도록 수정하는 과정에서 삽질을 반복하면서 결국 제한시간을 초과했다. 부끄러울 따름이다.

25: Fighting the Zombies

좌표평면에 좀비를 나타내는 점이 개 주어진다. 이 좀비들에 대해 임의의 원 안에 들어있는 좀비들을 임의의 변위로 평행이동한 뒤 주어진 크기의 정사각형을 잘 위치해 최대한 많은 좀비가 정사각형 안에 위치하도록 해야 한다.

좀비의 이동은 임의의 크기의 원을 기준으로 하므로 충분히 큰 원을 적절한 위치에 잡으면 원의 경계는 직선이나 다름없어진다. 이를 이용해 임의의 두 정사각형을 빠져나가는 좀비 없이 항상 겹칠 수 있음을 증명할 수 있는데, 개의 좀비 중 넷을 이용해 두 정사각형을 결정하고 두 정사각형에 들어있는 좀비의 합집합의 크기의 최댓값을 구하면 된다.

시간복잡도는 로 여유롭지는 않지만 제한시간 내에 제출은 가능하다. 대회중에는 풀이에 근접은 했으나 해답 완성과 구현의 가성비가 떨어진다고 생각해 마지막 문제로 바로 넘어갔다.

40: Beach Umbrellas

직선상에 1m 간격으로 있는 개의 구멍에 다양한 반지름의 우산 개를 꽂으려고 한다. 우산끼리 겹치지 않도록 주어진 우산을 모두 꽂는 방법의 수를 구해야 한다.

먼저 가장 왼쪽 또는 오른쪽의 우산 역시 우산 전체가 개의 구멍들이 이루는 선분에 완전히 포함되어야 한다고 생각해 보자. 선분은 길이의 구간이며, 각 우산이 겹치지 않기 위해서는 지름에 해당하는 구간이 필요하다. 에서 각 우산의 지름에 해당하는 길이를 모두 빼고 남는 구간의 길이를 이라고 하면 문제는 개의 서로 다른 점과 개의 동일한 구간의 순서를 배치하는 문제가 된다. 답은 가지이다.

문제는 가장 왼쪽 또는 오른쪽의 우산의 경우 바깥쪽을 향한 절반은 다른 우산과 겹쳐질 일이 없으므로 구간이 필요하지 않다는 점이다. 이를 고려하기 위해서는 가장 왼쪽과 오른쪽의 우산을 미리 정해 놓은 뒤 해당 우산들은 반지름만큼의 구간이, 다른 우산들은 지름만큼의 구간이 필요하다고 생각하여 계산해야 한다. 미리 정해진 우산의 크기에 따라 의 값이 변할 수 있으며, 답은 가지이다.

수식의 값을 계산하는 과정에서 결과값이 매우 커질 수 있으므로 로 나눈 나머지를 구해야 하는데 나눗셈은 modular inverse를 구해 곱해야 하며 이 소수이므로 굳이 Extended Euclidean algorithm을 구현할 필요 없이 페르마의 소정리를 이용해 쉽게 구할 수 있다. 또한 이 최대 까지 커질 수 있으므로 필요한 팩토리얼 값을 일일히 계산하지 말고 적절한 최적화 과정을 거쳐야 한다.

구현한 코드의 시간복잡도는 가장 큰 우산의 반지름을 라 할 때 이지만 코드의 효율성을 자신할 수 없어 Python 2로 구현, PyPy로 실행했다. 직접 만들어 본 데이터 셋을 수행하는데 약 25초, 실제 데이터 셋을 수행하는데 약 2초가 걸렸으며 각각 CPython으로 실행했을 때보다 수십배가량 빠른 속도였다.

L = 1000000007

def power(n, p):
    if p == 0:
        return 1
    r = power(n, p >> 1) ** 2
    if p & 1:
        r *= n
    return r % L

DI = {}
def modinv(n):
    if n in DI:
        return DI[n]
    DI[n] = power(n, L - 2)
    return DI[n]

def init(n, m):
    global DV, DC
    if m < 0:
        m = 0
    t = modinv(n) * modinv(n - 1)
    t %= L
    for i in xrange(1, n + 1):
        t *= i + m
        t %= L
    DC = [t]
    DV = m

DC = []
DV = 0
def calc(n, m):
    if m < 0:
        return 0
    for i in xrange(DV + len(DC), m + 1):
        DC.append((DC[-1] * (n + i) * modinv(i)) % L)
    return DC[m - DV]

for tc in xrange(int(raw_input())):
    DC = []
    N, M = map(int, raw_input().split())
    R = [int(raw_input()) for _ in xrange(N)]

    C = {i: 0 for i in set(R)}
    S = 0
    for i in R:
        C[i] += 1
        S += i

    if N == 1:
        A = M
    else:
        m = (M - 1) - (S * 2)
        A = 0
        init(N, m)
        for lm, lc in C.items():
            for rm, rc in C.items():
                if lm == rm and lc < 2:
                    continue
                m += lm + rm
                a = calc(N, m)
                if lm == rm:
                    c = lc
                    a *= c * (c - 1)
                else:
                    a *= lc * rc
                A = (A + a) % L
                m -= lm + rm

    print("Case #{}: {}".format(tc + 1, A))