백준 13034호: 다각형 게임(Sprague-Grundy 정리)

문제 링크: #13034: 다각형 게임(acmicpc.net)

이 문제는 두 사람이 폴리곤 게임을 하고 둘 다 가장 이상적인 방식으로 행동할 때 누가 이기는지를 알아내는 것입니다.
여기서 폴리곤 게임은 N 꼭지점으로 구성된 볼록 폴리곤입니다.
매 턴 교대로 두 점을 선택하여 선분을 그립니다.
여기서 선분이 이미 그린 선분과 교차한다면 그 점에서 교차하지도 않아야 합니다.
선분을 번갈아 그려서 더 이상 선을 그릴 수 없는 경우 플레이어는 해당 라운드에서 패배합니다.

이 문제를 풀기 위해서는 Sprague-Grundy 정리와 Grundy 수를 알아야 합니다.
Grundy 번호를 간단히 설명하기 위해 현재 점수를 숫자로 대체합니다.
Grundy 숫자 0은 게임의 최종 상태(승패가 결정되는 상태)로 간주되며 게임의 다양한 상태는 플레이어가 수행하는 작업에 따라 1, 2, 3…과 같은 숫자가 할당됩니다.
할 수 있다.
. 성공적인 전략 게임: Sprague-Grundy 정리(casterian.net) 자세한 설명을 보고 배울 수 있었습니다.
주어진 상태의 기본 y 수를 할당하는 절차는 k가 주어진 상태에서 나올 수 있는 다음 상태의 기본 y 수의 집합인 경우 존재하지 않는 가장 작은 음이 아닌 정수를 k에 할당하는 것입니다.
된다.
이것을 멕스라고도 합니다.

상태

이것은 N개의 게임이 동시에 플레이될 때 문제가 됩니다.
플레이어 A와 B가 동시에 숫자 1과 2로 x와 y 게임을 하고 있다고 가정합니다.
A는 세 가지 가능한 조치가 있습니다.
x에서 1 -> 0, y에서 2 -> 1 또는 y에서 2 -> 0. A가 이기려면 어떻게 해야 합니까? 답은 y의 2 -> 1입니다.
이렇게 하면 x:1, y:1이 되고 B는 반드시 x 또는 y를 0으로 만들어야 합니다.
그러면 A가 나머지를 0으로 설정하면 x:0, y:0 상태인 B는 무조건 패배한다.

한편 그런디의 숫자가 2, 2인 게임이라고 치자. A가 취할 수 있는 조치는 4가지가 있지만 머리 속으로 계산하면 어떤 조치를 취하든 지게 됩니다.
그러면 Grundy 숫자 1과 2의 상태가 크게 다른 것을 볼 수 있습니다.
특히 N 게임을 동시에 플레이할 때 그렇습니다.

N 게임을 함께 할 때 각 게임 상태에서 Grundies의 수와 N Grundy 숫자를 XOR할 수 있다고 합니다.
여기서 XOR의 결과는 Grundy 숫자 1 또는 2에 따라 다르므로 위와 같은 결과가 나옵니다.
그럼 본격적으로 문제 해결을 시작하겠습니다.

이 문제를 대체하면 지저분한 숫자 0은 더 이상 선분을 그릴 수 없으며, 그 턴에 그런 숫자가 0이면 그 턴의 플레이어는 패배합니다.
이제 N개의 정점이 있을 때 Grundy 수를 고려해 봅시다.

N=1이면 점이 하나뿐이므로 선분을 그릴 수 없습니다.
Grundy 번호는 {0}입니다.

N=2이면 점이 두 개이므로 먼저 선분을 그릴 수 있습니다.
Grundy 번호는 {0, 1}입니다.

N = 3이면 3점이 있으므로 먼저 그리면 1개가 남습니다.
Grundy 번호는 {0, 1}입니다.

N = 4이면 4개의 점이 있습니다.
따라서 가운데를 먼저 그리면 더 이상 그릴 수 없고 인접한 정점을 그리면 다른 정점을 그릴 수 있습니다.
그런 다음 N = 4의 초기 상태는 {0, 1}을 제공할 수 있습니다.
mex()를 실행할 때 가장 빠른 Grundy 번호는 2입니다.

N개의 점이 있을 때 두 개의 정점을 선택하면 나머지 정점은 두 개의 그룹으로 나뉩니다.
분할할 그룹의 정점 수는 (0, N-2), (1, N-3), (2, N-4) ..( (N-2)/2 , ( N -2)/2 ) 될 그룹이 분할되었다고 말하는 것이 안전하므로 두 게임이 함께 ​​플레이되므로 XOR 연산이 각각의 경우 Grundies의 수를 얻을 수 있습니다.
이와 같이 각각의 경우에 대한 그런디 숫자 집합을 찾아 mex()를 사용하면 해당 상태에 대한 그런디 숫자를 찾을 수 있습니다.

import sys

N = int(sys.stdin.readline().rstrip())

grundys = (-1 for _ in range(1001))

grundys(0) = 0
grundys(1) = 0
grundys(2) = 1

for i in range(3, 1001):
    cur = (0 for _ in range(1001))
    for j in range(i//2 + 1):
        left = j
        right = (i - 2) - j
        cur(grundys(left)^grundys(right)) = 1
        
    for k in range(i):
        if cur(k) == 0:
            grundys(i) = k
            break
        
if grundys(N) == 0:
    print('2')
else:
    print('1')

이 문제에서 N은 1000에 불과하므로 grundy(0), grundy(1), grundy(2)를 할당하고 루프를 사용하여 3에서 1000까지 i를 계산합니다.
() grundy(i)를 얻습니다.
코드 구현은 쉬웠지만 그런디 넘버는 이해하기 어려웠다.