사용자 도구

사이트 도구


ps:problems:boj:16877

핌버

ps
링크acmicpc.net/…
출처BOJ
문제 번호16877
문제명핌버
레벨플래티넘 3
분류

스프라그-그런디 정리

시간복잡도O(m+nlogn)
인풋사이즈m<=10^5, n<=3*10^6
사용한 언어Python
제출기록62224KB / 3244ms
최고기록3244ms
해결날짜2022/06/08

풀이

  • 님 게임의 변형. 스프라그-그런디 정리를 적용해서 풀면 된다.
  • 돌 갯수에 따른 그런디수는 클로즈드 폼으로 식이 정리되지 않는다.. DP형태로 일일히 계산해줘야 한다.
  • 돌 n-1개까지의 그런디수가 구해져있을때, 돌 n개에 대한 그런디 수를 구하기 위해서는, 여기서 n-1, n-2, n-3, n-5, n-8, … 에 대한 그런디수들의 mex값을 찾아야 한다. n이하의 피보나치수는 O(logn)개 있으므로 시간복잡도는 O(logn)이다. 돌 1개~n개까지의 그런디수를 모두 구하려면 O(nlogn)이 걸린다
  • 돌더미 한개의 그런디수를 모두 구해놓고 나면, 돌더미 m개의 그런디수를 구하는 것은 그냥 xor해주면 되므로 O(m). 총 시간복잡도는 O(m+nlogn).
  • 그렇지만, 파이썬으로 통과시키기에는 시간이 꽤 빡빡하다. n이 최대 3,000,000까지 가능하고. 이것은 32번째와 33번째 피보나치수의 사이에 있는 숫자이다. 대충 가져갈수 있는 돌의 갯수를 평균 25개 정도라고 가정하고 보면.. 가장 깊은 루프는 75,000,000 번 정도 돈다는건데.. 아예 불가능할건 아닌것 같으면서도 만만치 않긴 하다.. pypy로는 700ms 정도에 통과된다.
    • 심지어 시간 제한도 1초가 아닌 0.5초이다. 파이썬으로 시간보너스를 받으면 3.5초가 되는 제한시간
  • 열심히 억지 최적화를 시도해보자.. 이것저것 다 시도했지만 의미가 있는 최적화는 두가지이다.
    • 그런디 수를 죽 나열했을때, 0 뒤에는 항상 1,2,3 이 온다.
      • 사실 0 뒤에는 매우 높은 확률로 0,1,2,3 아니면 0,1,2,3,4,5가 된다.. 그러나 100% 성립하는 것은 0뒤에 1,2,3이 온다는 것까지만이다.
    • mex를 비트연산으로 구할수 있다.
      • 보통은 모든 값이 False로 초기화 된 배열 x[]를 만들고, 다음 스테이트들의 그런디 수들 g_i에 대해서 x[g_i] = True 로 체크한다음, x배열을 인덱스 0부터 순회하며 x[i]==False 인 가장 작은 i를 찾는 식으로 처리한다
      • 비트연산을 이용하면, x를 다음 스테이트의 그런디수에 해당하는 비트들만 1로 채워진 비트마스크로 표현한다. ~x에서 LSB의 위치가 mex가 된다. 파이썬에서는 비트를 비트마스크에 세팅하는 것이 배열을 채우는것보다 별로 빠르지 않지만, LSB를 찾는것은 (x&-x)로 확실히 빠르게 처리 가능하다.
    • 이 외에도 몇몇 사소한 최적화들을 동원해서 3244ms에 통과시키는 것에 성공했다..

코드

"""Solution code for "BOJ 16877. 핌버".

- Problem link: https://www.acmicpc.net/problem/16877
- Solution link: http://www.teferi.net/ps/problems/boj/16877

Tags: [Sprague-Grundy]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    P = [int(x) for x in input().split()]

    max_p = max(P)
    fibo_nums = [2, 3]
    while fibo_nums[-1] < max_p * 2:
        fibo_nums.append(fibo_nums[-1] + fibo_nums[-2])

    grundy = [0b1]
    fibo_index = []
    while (i := len(grundy)) <= max_p:
        while i >= fibo_nums[0]:
            fibo_index.append(-fibo_nums.pop(0))
        next_grundy_nums = grundy[-1]
        for ind in fibo_index:
            next_grundy_nums |= grundy[ind]
        x = ~next_grundy_nums
        grundy_i = (x & -x)
        grundy.append(grundy_i)
        # If grundy[i] is 0, grundy[i+1:i+4] is [1,2,3].
        if grundy_i == 0b1:
            grundy.append(0b10)
            grundy.append(0b100)
            grundy.append(0b1000)

    grundy_num = 0
    for p_i in P:
        grundy_num ^= (grundy[p_i].bit_length() - 1)

    print('koosaga' if grundy_num > 0 else 'cubelover')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Z A D M F
 
ps/problems/boj/16877.txt · 마지막으로 수정됨: 2022/06/08 16:29 저자 teferi