[BOJ 33160] 꽃 풀이

 안녕하세요, 어제 플래를 하나밖에 풀지 않은 관계로 급하게 출제한 문제의 풀이라도 작성해 봅니다.

 

 이 문제는 선형 구조일 때 $O(N)$풀이가 존재해서, 트리 구조에서도 정해보다 빠른 시간 복잡도로 해결해 주시는 분이 등장하기를 기대하고 있었는데, 그냥 풀리지 않아서 아쉬움을 느끼고 있습니다. 많은 고수분들이 풀어주셨으면 좋겠습니다.

 

 *문제의 사전지식으로 Sprague_Grundy theorem을 요구합니다.

 우선 문제를 보면 부모가 자식보다 가중치가 큰 트리 구조가 주어지고, 각 정점의 가중치들을 번갈아가며 줄여나가는 문제라고 볼 수 있습니다. 다만 트리 구조에서 먼저 생각하는 것은 어렵기 때문에, 우선 선형 구조라고 가정하고 문제를 해결해 봅시다.

 $i$번 노드의 부모가 $i-1$번이라고 할 때, 조건에서 $A_{i-1} \ge A_i$입니다. 따라서 $i$번 칸의 높이가 $A_i$인 격자를 생각해 보면 다음과 같이 높이가 단조감소하는 모습이 됩니다.

 

 격자의 각 칸에, 트리의 상태가 해당 위치일 때 그런디 값을 저장하고자 합니다. 트리의 상태가 해당 위치라는 것은 다음을 의미합니다.

• 현재 위치보다 왼쪽에 위치한(부모) 노드들의 남은 가중치는 $0$이다.
• 현재 위치의 노드의 남은 가중치는 현재 위치를 포함하여 위쪽에 위치한 칸의 수이다.
• 현재 위치보다 오른쪽에 위치한 노드들의 남은 가중치는 각 위치에서 현재 위치를 포함하여 위쪽에 위치한 칸의 수이다.

 예를 들어,  현재 위치가 다음그림에서 빨간색 지점이라고 하면, 현재 각 노드의 남은 가중치는 주황색으로 표시한 영역이 되며, $(0, 0, 6, 5, 1)$ 만큼의 가중치가 남아있습니다.

 

 위와 같이 그런디 수를 정의를 하면, 현재 위치가 영역의 바깥이라면 더 이상 트리에 남은 가중치가 없어지는 상태이므로 그런디 수가 $0$이고, 영역의 안쪽이라면 $\operatorname{mex} (\{한\,칸\,위의\,그런디\,수,\,한\,칸\,오른쪽의\,그런디\,수\})$가 됩니다.

 왜냐하면, 게임에서 할 수 있는 행동이 $2$가지 존재하는데, 서브트리 전체의 가중치를 $1$줄이는 것은 위 격자에서 한 칸 위로 이동하는 것과 동치이며, 트리의 부모 노드의 가중치를 $0$으로 만드는 것은 한 칸 오른쪽으로 이동하는 것과 동치이기 때문입니다.

 

 따라서 위 그림과 같이 선형 구조에서는 각 칸의 그런디 수를 채워나가면 $O(NA)$의 시간복잡도로 해결할 수 있습니다. 트리 구조에서는 자식들이 부모로 합쳐지는 지점에서만 잘 계산해 주면 됩니다.

 서브트리 전체의 가중치를 $1$줄이는 것은 전과 같이 한 칸 위로 이동하는 것과 동치입니다. 단, 트리의 부모 노드의 가중치를 $0$으로 만드는 행동은 각 자식 노드들에서 얻을 수 있는 그런디 수를 bitwise XOR 한 값으로 그런디 수가 변합니다. 따라서 트리 구조에서도 naive 한 계산으로 $O(NA)$에 계산할 수 있습니다.

 또한, 위 과정에서 트리의 모든 위치의 그런디 수는 단 2개의 값의 $\operatorname {mex}$로만 구해지기 때문에, 그런디 수는 항상 $2$이하입니다.

 

 이제 시간복잡도에서 $A$를 제거하기 위한 관찰을 해봅시다. 만약 트리가 정점 하나인 트리라면, 위와 같이 그런디 수를 채우는 테이블에서 위부터 $(1, 2)$가 반복되는 구조입니다. 즉, 기저는 길이 $2$의 사이클이 반복됩니다.

 트리의 각 정점의 그런디 수를 구할 때, 자식 노드들의 그런디 수를 통해 부모 노드의 그런디 수가 결정된다는 것을 알 수 있는데, 길이 $2$인 사이클이 크기가 $2$ 이하인 특정 수와 만나서 나오는 테이블을 계산해 보면 다음과 같습니다. (이때, 자식 노드들의 가중치가 $0$, $1$, $2$중 하나이며, $1 \oplus 2 = 3$이기 때문에 길이 2인 사이클에서는 값들이 $3$까지 커질 수 있습니다.)

 

 이때, 왼쪽 괄호 안의 값 $3$개가 각각 (특정 수, 사이클의 첫 번째 값, 사이클의 두 번째 값)을 의미하며, 여기서 특정 수란 다음과 같은 그림에서 빨간색 영역의 그런디 수들을 구하기 위해 필요한 노란 칸의 그런디 수를 의미합니다.

 

 위 테이블을 보면 몇 개의 쌍을 제외하고는 길이 $2$의 사이클이 반복되며, 그 몇 개의 쌍 또한 앞의 $1$개 또는 $2$개의 값을 제외하면 이후에는 길이 $2$의 사이클이 반복된다는 사실을 알 수 있습니다.

 따라서 구간들을 합쳐줄 때 위와 같은 정보들을 통해 앞의 $2$개의 칸을 따로 떼어 구간을 생성하고, 이외의 구간을 (시작높이, 끝 높이, 사이클의 두 값)을 저장하면서 스위핑을 계속해주면, 노드당 구간의 개수는 $N^2$개 정도가 생성이 되며 전체 노드의 개수가 $N$개이므로 $O(N^3)$에 문제를 해결할 수 있게 됩니다.

 

 

 

 +여담으로, 지문에 등장하는 호시와 유키가 어디서 나왔냐고 묻는 분이 있어서 남깁니다.

 제가 어릴때부터 좋아하던 花と星の雪이라는 제목의 노래가 있습니다. 이거 자체를 제목으로 하고 싶었는데 도저히 지문 아이디어가 떠오르지 않았고, 결국 花을 제목으로, 星와 雪를 등장인물로 설정해서 끼워 맞췄습니다. 정말 좋은 노래이니 한 번씩 들어주세요 :D