[Python] 19114번 Master Zhu and Candies (증명 추가 필요)

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

19114번: Master Zhu and Candies

---

 

23/05/03

 

 

전형적인 스프라그-그런디 정리 문제로, 문제에서 주어지는 그대로 착실하게 구현하면 된다.

 

게임판 분할에 대한 선행 지식이 필요하다.

---

 

문제 접근 방식:

 

 

문제에서 주어지는 그대로를 구현하면 된다.

 

근데 기존의 님 게임과 한가지 달라진 점은 내가 할 수 있는 행동에 "게임판을 분할하는 행동"이 추가되었다는 점이다.

 

$3$개의 게임판으로 분할하는데, $3$개는 모두 빈 게임판이 아니어야 한다.

 

예를 들어, $8$개의 캔디 더미가 있으면 내가 할 수 있는 행동은 "더미에 $0$~$7$개의 캔디가 있는 상황 만들기" + "$(1, 1, 6)$ 처럼 캔디 더미를 $3$개로 쪼갠 상황 만들기"이다.

 

당연히, 그런디 수는 캔디 더미의 캔디 개수와 같지 않다.

(이 부분을 유념해야 할 것이다. 님 게임과는 다르게 할 수 있는 행동이 다르기 때문이다.)

 

 

 

그러면 $8$개의 캔디가 놓인 상황에 대한 그런디 수는 어떻게 구할까?

 

이는 스프라그-그런디 정리를 배웠다면 알다시피, $mex$함수를 통해 재귀적으로 구현하면 된다.

 

또한, $(1, 1, 6)$처럼 캔디 더미를 $3$개로 쪼갠 상황에 대한 그런디 수는 그 캔디 더미에 대한 그런디 수를 모두 $XOR$하면 구할 수 있다.

 

(편의상 $grundy(x) = g(x)$로 표기하겠다.)

 

따라서 $g(8) = mex(g(0), g(1), ... g(7), g(1) \oplus g(1) \oplus g(6), ... , g(6) \oplus g(1) \oplus g(1))$이 된다.

 

 

 

근데 이걸 그대로 구현하면 시간초과가 날 것이다.

 

왜냐하면 캔디 더미를 $3$개로 쪼개는 모든 경우의 수가 매우 많기 때문이다.

 

캔디의 개수 제한은 최대 $10^9$개 까지 이므로, 모든 경우의 수를 따져보기에는 현실적으로 불가능하다.

 

따라서, 이 문제는 그런디 수가 일정 주기를 가진다는 "믿음"이 있어야 풀 수 있는 문제이다.

 

 

 

실제로 $100$개 정도 까지 직접 그런디 수를 구현해 보면, 일정한 주기를 가지고 반복된다는 사실을 알 수 있다.

 

이를 통해 문제를 해결할 수 있다.

 

(증명은 아직 하지 못한 상태이므로 왜 그런지 증명을 한다면 글을 보충하겠습니다.)

---

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

# 19114번 Master Zhu and Candies
# 게임 이론, 스프라그-그런디 정리

import sys
input = sys.stdin.readline

N = int(input())
S = list(map(int, input().rstrip().split()))

total = 0
for s in S:
    if s % 8 == 7:
        total ^= (s+1)
    elif s % 8 == 0:
        total ^= (s-1)
    else:
        total ^= s

print('First' if total else 'Second')