[Python] 16899번 채석장 게임

https://www.acmicpc.net/problem/16899

16899번: 채석장 게임

---

 

22/10/13

 

 

전형적인 nim게임으로, 그냥 XOR을 하면 시간 초과가 나는 문제이다.

 

XOR연산의 성질을 이용해야 풀 수 있는 영리한 문제이다.

---

 

문제 접근 방식:

 

 

문제의 조건을 자세히 살펴보면, N의 크기가 최대 10만이고, Mi가 최대 10의 16승까지 있으므로, 그냥 모든 숫자들을 XOR 연산시키려고 한다면 무조건 시간 초과가 난다.

 

https://www.acmicpc.net/problem/10464

10464번: XOR

이 문제를 만약 풀었었다면, 이 문제의 풀이를 응용하여 쉽게 풀 수 있다.

 

연속이면서 mod 4에 대해 모두 다른 값을 가지고, 4로 나누면 같은 몫을 가지는 숫자 4개(예를 들어 0, 1, 2, 3)를 모두 XOR연산 취해주면 0이 나오게 되는데, 이를 응용해서 문제를 해결할 수 있다.

 

XOR연산을 하는데, 위의 성질을 이용해 굳이 연산을 안 해도 되는 중간 숫자들을 4개씩 묶어서 연산을 하지 않아도 되기 때문이다.(0과 xor 하면 항상 원래 숫자가 나오기 때문)

 

그래서 xor연산을 시작하는 숫자가 mod 4에 대해서 몇이 나오는지, 그리고 몫이 얼마가 나오는지(몇 번째 그룹에 속해있는지)를 구하고, xor연산을 끝내는 숫자가 mod 4에 대해서 몇이 나오는지, 몫이 얼마가 나오는지를 구해서 중간의 연산들을 모두 건너뛰고 연산을 하면 된다.

 

예를 들어, 2부터 114325까지 XOR연산을 취한다고 하면, 2^3^4^5^...^114323^114324^114325를 하려면 시간이 무지막지하게 걸린다.

 

따라서 2가 어디위치해있는지 보면, 2는 몫이 0이고 나머지가 2이므로, 같은 몫을 가지는 3까지 XOR 연산한다.

 

이후 중간에 4^5^6^7^...^114320^114321^114322^114323까지는 전부 4개씩 묶여 0으로 나오기 때문에 연산할 필요가 없다.

 

이후 114325가 어디위치해있는지 보면, 114325는 몫이 28581이고, 나머지가 1이므로 같은 몫을 가지는 114324부터 해당 숫자까지 연산하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16899번 채석장 게임
# 게임 이론, 스프라그-그런디 정리
'''
XOR 취하기
'''
import sys
input = sys.stdin.readline
total_val = 0
for _ in range(int(input())):
    X, M = map(int, input().rstrip().split())
    start, end = X, X+M-1
    group_s = start//4
    remain_s = start%4
    group_e = end//4
    remain_e = end%4
    total = 0
    for i in range(start, start+(4-remain_s)):
        total ^= i
    for j in range(group_e*4, end+1):
        total ^= j
    total_val ^= total
print('koosaga' if total_val else 'cubelover')