[Python] 32213번 래빗 홀

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

---

 

24/09/05

 

 

간단한 스프라그-그런디 문제이다. 관찰의 아이디어가 좋아서 작성해본다.

---

 

문제 접근 방식:

 

 

두 사람이 할 수 있는 행동은 동일하다. 둘 중 하나이다.

 

1번 행동은 일반적인 님 게임이다. 근데 걸리는 점은 2번 행동이다.

 

2번 행동이 1번 행동에 영향을 줄 수 있을까, 곰곰히 생각해보면 아니다.

 

얼핏 생각하면 영향을 줄 수 있을 것 같지만 2번 행동이 전체 XOR의 합에 영향을 끼치지 못하므로 1번 행동과 독립이다.

 

결국 2번 행동은 홀짝성에 관한 게임을 개별적으로 하는 것과 동치이다.

 

즉, 님 게임과 홀짝 게임을 동시에 하고 있는 것과 동치이다.

 

처음에는 이러한 사실 때문에 님게임 XOR값과 홀짝성 모두 만족하면 후공 승리라고 판단했다. 근데 틀렸다.

 

근데 생각해보면 홀짝 게임도 일종의 님게임이다. 따라서 and연산이 아닌 XOR연산을 해주면 맞았습니다를 받을 수 있다.

---

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

# 32213번 래빗 홀
# 스프라그 그런디
import sys
input = sys.stdin.readline
from functools import reduce

T = int(input())
for _ in range(T):
    N = int(input())
    A = reduce(lambda a, b: a^b, map(int, input().split()))
    if ((N-1)%2)^A == 0:
        print('tweede')
    else:
        print('eerste')