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()
ps/problems/boj/16877.txt · 마지막으로 수정됨: 2022/06/08 16:29 저자 teferi
토론