[Python] 32233번 토러스 게임 조작하기

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

---

 

24/09/12

 

 

오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다.

 

맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다.

---

 

문제 접근 방식:

 

 

이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다.

 

1. 오일러 지표에 대한 지식

 

2. 스프라그-그런디 정리에 대한 지식

 

3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식.

 

 

먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다.

 

이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.

 

하나의 게임을 님버로 어떻게 치환할 것인가가 주된 요점이 될 것이다.

 

이 님버는 당연히 그래프의 평면성과 관련이 있을 것이다. 엄밀히 말하면, 토러스 위에서는 평면성이라고 말하기가 곤란하므로, 평면 위에서와 토러스 위에서 그래프 임베딩이 가능한 경우와 관련이 있을 것이다.

 

구는 오일러 지표 상 평면과 동일한 취급을 할 수 있고, 정점의 개수 $N$이 주어져 있을 때 그을 수 있는 최대 간선의 개수는 $3N-6$개이다.

https://en.wikipedia.org/wiki/Planar_graph#Maximal_planar_graphs 

Planar graph - Wikipedia

이는 오일러 지표를 통해 쉽게 유도할 수 있으며, 이러한 Planar graph를 Maximal planar graph라고 부른다.

 

물론 $N = 2$일때는 최대 $1$개까지 그을 수 있다.

 

토러스에서 정점의 개수 $N$이 주어져 있을 때 겹치지 않도록 그을 수 있는 최대 간선의 개수는 $3N$이다.(이러한 그래프를 Toroidal graph라고 부른다.)

https://mathworld.wolfram.com/ToroidalGraph.html

Wolfram MathWorld: The Web's Most Extensive Mathematics Resource

 

예외적으로 $2 \leq N \leq 7$인 경우, 그을 수 있는 최대 간선의 개수는 $N(N-1)/2$개이다.

 

근데 검색을 좀 하다보면, $3N$개의 간선을 가지고 있지 않음에도 불구하고 더 이상 간선을 겹치지 않도록 간선을 추가할 수 없는 그래프의 예시가 나온다.

 

https://www.researchgate.net/figure/A-maximal-toroidal-graph-that-is-not-a-triangulation-of-the-torus-10_fig2_353996065

이 그래프의 경우가 그런데, 사실 님버의 정의를 잘 생각해보면 이 그래프랑은 무관하게 $3N$이 님버라는 사실을 확인할 수 있다.

 

왜냐하면 님버는 재귀적으로 이전 상태로 모두 갈 수 있냐, 즉, 이전 상태의 님버들의 mex값으로 정의되기 때문이다.

 

이 그래프를 만들 수도 있고, 최대 간선을 가지는 그래프의 상태도 만들 수 있는 어느 분기점 상태가 있을 것인데, 이 분기점 상태의 님버는 mex에 의해 최대 간선을 가지는 그래프의 상태 쪽의 님버로 따라갈 것이기 때문이다.

 

결론적으로, 하나의 토러스와 하나의 구에 대해서 정점이 주어졌을 때의 님버를 구할 수 있다.

 

 

다시 되돌아가서, 우리가 원하는 것은 후공이 처음 상태를 조작해서 선공의 님버의 XOR합이 $0$이 되게끔 만들 수 있냐를 판단하는 것이다.

 

먼저, 토러스에 대한 님버(이를 편의 상 토러스 님버라고 하겠다.)를 전부 XOR한 값이 $0$이라면, 구할 필요가 없다. 토러스를 조작하지 않고 그냥 게임을 진행하면 된다.

 

만약 토러스 님버를 전부 XOR한 값이 $0$이 아니라면, 몇 개의 토러스를 구로 바꾸어서 $0$이 되게끔 만들고 싶은 것이다.

 

편의 상, 토러스 님버를 $A_1, A_2, \dots, A_n$이라고 하고, 구 님버를 $B_1, B_2, \dots, B_n$이라고 하자.

 

그리고 토러스 님버를 모두 XOR한 값을 $S$라고 하자.

 

만약 몇 개의 토러스를 골라서 구로 바꿔서 $0$이 되게 만들 수 있다고 해보자. 그리고 그 토러스의 인덱스의 집합을 $K$라고 하자.

 

그러면 XOR의 성질에 의해 다음이 성립한다.

$$A_1 \oplus A_2 \oplus \cdots \oplus A_n \bigoplus_{i \in K} (A_i \oplus B_i) = S \oplus \bigoplus_{i \in K} (A_i \oplus B_i) = 0$$

 

편의 상 $C_i = A_i \oplus B_i$라고 한다면, 다음과 같은 문제로 재정의 할 수 있다.

 

$C_i$들 중 일부분을 선택하여 모두 XOR한 값이 $S$가 되게 끔 만들 수 있냐?

 

이는 이진법 위에서의 가우스 소거법을 적용하면 된다.

 

이진법 위에서는 XOR이 덧셈의 역할을 하므로, $C_i$를 선택을 하냐 안하냐를 $0$과 $1$로 표현하여 해당하는 벡터를 구하면 된다.

 

비슷한 이야기지만, 나의 경우 XOR basis의 개념을 사용하여 가우스 소거법을 조금 돌아가서 구현했다.

https://usaco.guide/adv/xor-basis?lang=cpp

 

$C_i$들을 만들 수 있는 Basis를 구성하고, $j$번째 Basis가 $C_i$들 중에서 어떤 것을 XOR해야 구성할 수 있는지도 구한다.

 

이후 $S$를 Basis로 표현할 수 있는 지 판단한다.

 

만약 표현할 수 있다면, Basis로 표현한다. 이전에 $j$번째 basis를 $C_i$들 중 어떤 것을 XOR해야 구성할 수 있는지를 구해놨으므로, 이를 통해 $C_i$를 복원한다.

 

---

코드는 생략.