[Python] 27852번 Kruskal

 

 

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

---

 

24/05/17

 

 

오랜만에 스프라그-그런디 정리 문제를 해결했기에 글로 작성해본다.

 

님 게임의 변형 문제로, 어떻게 해야 님 게임으로 치환할 수 있을지를 고민해볼 수 있는 좋은 문제이다.

---

 

문제 접근 방식:

 

 

문제에서 제시하는 상황은 다음과 같다.

 

일반적인 님 게임과 비슷하게, 돌 더미들이 여러 개 주어져 있다. 대신, 한 플레이어가 $1$개부터 $K$개까지 돌을 가져갈 수 있으며, 승리 조건이 어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기게 되는 게임으로 바뀌었다.

 

두 플레이어가 최선의 플레이를 진행한다고 할 때, 누가 이길 지를 판별하는 것이 문제의 요구조건이다.

 

님 게임의 변형으로 돌 개수의 제한을 두는 문제는 약간 흔하다.

 

위와 같이 연속된 숫자 $1$부터 $K$개까지 가져갈 수 있는 문제라면, 그런디 수는 $K+1$의 주기를 가지고 있다.

 

중요한 건, 승리 조건이다.

 

어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기므로, 예를 들어, 어느 한 돌더미가 $35$개라면, $35$보다 작으면서 가장 가까운 소수인 $31$을 만드는 즉시 이긴다고 생각할 수 있다.

 

근데 왜 굳이 가장 가까운 소수라고 했을까?

 

잘 생각해보면, 자신의 차례 때 $31$개보다 더 작아지도록 굳이 돌을 가져갈 이유가 없다.

 

그냥 $31$개를 만들어버리면 이기기 때문이다.

 

따라서, 실질적으로 남은 돌 더미들을 계산할 수 있는데, 이는 각 돌 더미들에서 그 수보다 작은 가장 가까운 소수를 빼주면 된다.

 

앞으로 언급되는 "돌 더미"라는 용어는 실질적으로 남은 돌 더미를 의미한다.

 

선공이 이길 수 있는 포지션은 어떠한 더미가 있어서, 이 더미의 돌을 전부 다 가져갈 수 있는 상황이다.

 

예를 들어, 최대 $5$개를 갈 수 있다고 하고, 돌 더미의 모습이 $3, 6, 8, 9, 10$이라고 하면, 선공이 $3$개짜리 돌 더미를 택해서 이 더미의 돌을 다 가져가면 된다.

 

그러면 그 경우가 아니라면 어떨까?

 

똑같이 $5$개를 가져갈 수 있는 상황인데, $9, 10, 11, 12, 13$개가 남아있다고 해보자.

 

내가 이기도록 상대방에게 강제를 하려면, 내가 이 돌 더미의 모습을 $6, 6, 6, 6, 6$으로 만들어주면 된다.

 

그렇게 되면 상대방이 어떤 돌 더미를 택하는 간에, $5$개보다 같거나 작은 돌 더미가 생기기 때문이다.

 

따라서, 다음과 같이 정리할 수 있다.

 

최대 $K$개 가져갈 수 있다고 하고, 돌 더미들 중에서 $K$개보다 작거나 같은 돌 더미가 존재한다면 무조건 선공이 이긴다.

 

그게 아니라면, 즉, 모든 돌 더미들이 $K$개보다 크다면 스프라그-그런디 정리를 적용한다.

 

이때, $K+1$의 그런디 수는 $0$이다.(선공이 지는 포지션이기 때문에)

 

$K+2, K+3, \cdots$의 그런디 수는 $1, 2, \cdots$이며, $K+1$의 주기를 가지며 반복된다.

 

단, 예외 처리를 진행해야하는데, 오직 하나의 돌 더미만 존재하고, 그 돌 더미의 개수가 "소수"라면, 실질적으로 남은 돌 더미의 개수가 $0$이 되어버리는 경우가 생긴다.

 

이러한 경우를 잘 예외처리 해주어야하며, $3$일 때는 항상 선공이 이김을 유의해주어야 한다.

---

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

# 27852번 Kruskal
# 소수 판정, 스프라그-그런디 정리
'''
접근 방법:
가장 가까운 소수를 빼준다.
그러면 실질적으로 남은 돌 더미들이 있다.
선공이 이길 수 있는 포지션은 어떠한 더미 중에서 전부 다 가져갈 수 있는 상황임
예를 들어, 최대 5개 가져갈 수 있고,
3, 6, 8, 9, 10개 남아있으면
선공이 3개 돌더미 선택해서 다 가져가면 됨.
그게 아닌 경우가 있다고 해보자.
예를 들어 최대 5개 가져갈 수 있는데,
9, 10, 11, 12, 13개 남아있다고 해보자.
"내"가 이기도록 상대방한테 강제하려면?
내가 6, 6, 6, 6, 6을 만들면 된다.
반대로 "내"가 지는 경우는?
상대방이 6, 6, 6, 6, 6을 먼저 만들어서 내가 어느걸 선택해도 5보다 작거나 같은
더미가 만들어 질때임.
그러면 어떻게 내가 6, 6, 6, 6, 6을 만들 수 있을까?
상대방 차례가 끝났는데
6, 6, 6, 6, (7, 8, 9, 10, 11)이 되면 되지 않을까?
6 -> 0
7 -> 1
8 -> 2
9 -> 3
10 -> 4
11 -> 5
12
'''
import sys
input = sys.stdin.readline
from functools import reduce

def Miller_Rabin_primality_test(N, a, s, d):
    if a >= N: a %= N
    if a <= 1: return True
    k = pow(a, d, N)
    if k == 1 or k == N-1: return True
    for r in range(1, s):
        k = pow(k, 2, N)
        if k == N-1: return True
    return False
def is_prime_with_Miller_Rabin(N):
    if N == 2: return True
    if N == 1 or N % 2 == 0: return False
    s, d = 0, N-1
    while d % 2 == 0:
        d //= 2
        s += 1
    if N < 4759123141:
        A = [2, 6, 61]
        for a in A:
            if not Miller_Rabin_primality_test(N, a, s, d):
                return False
        return True
    A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in A:
        if not Miller_Rabin_primality_test(N, a, s, d):
            return False
    return True
def mex(S):
    for i, j in zip(sorted(S), range(len(S))):
        if i != j: return j
    return len(S)
def solve():
    N, K = map(int, input().split())
    if N == 1:
        Ai = int(input())
        if Ai == 3:
            print('YES')
            return
        j = 1
        while True:
            if is_prime_with_Miller_Rabin(Ai - j):
                break
            j += 1
        if j <= K:
            print('YES')
            return
        if (j-K-1)%(K+1):
            print('YES')
        else:
            print('NO')
        return
    A = []
    Real_stone = []
    for _ in range(N):
        Ai = int(input())
        A.append(Ai)
    for Ai in A:
        j = 0
        while True:
            if is_prime_with_Miller_Rabin(Ai - j):
                break
            j += 1
        if j <= K:
            print('YES')
            return
        Real_stone.append((j-K-1)%(K+1))
    ans = reduce(lambda x, y : x^y, Real_stone)
    print('YES' if ans else 'NO')
for _ in range(int(input())):
    solve()