queued_q   3년 전

이 문제에서 쉽게 떠오르는 전략으로 "인접한 노드의 색깔 다양성이 높은 곳부터 색칠하기"나 이와 유사한 전략들을 생각할 수 있지만, 이러한 전략들은 파훼가 가능합니다. 좋은 문제지만 아쉽게도 채점기가 약해서 이런 전략들이 통과되는 것으로 보입니다...

노드 u의 인접한 노드의 색깔 다양성을 div(u)라고 합시다. div가 높은 노드부터 색칠하는 전략을 쓰는 플레이어를 A, 이 전략을 파훼할 플레이어(인터랙터)를 B라고 합시다. 이제 아래와 같은 그래프를 생각합시다.

      / 1 - 2 - 3
     // 4 - 5 - 6
y - x - 7 - 8 - 9
    | \ 10 - 11 - 12
    |
    |       f
    |       |
a - b - c - d - e
    |       |
    g       h

A가 맨 처음 y를 색칠했다고 가정하고, B는 2, 5, 8, 11을 차례로 색칠합니다. A는 전략에 따라 3, 6, 9, 12를 색칠합니다. 이제 B가 x를 색칠하면, div=2인 노드가 한 번에 4개 생기게 됩니다 (1, 4, 7, 10). A가 이들을 모두 색칠하는 동안, B는 f, g, h, 그리고 마지막으로 c를 색칠합니다. 그러면 동시에 div(b)=div(d)=3을 만들 수 있습니다. A가 b를 색칠할 경우 B는 e를 색칠해서 div(d)=4를 만들 수 있고, A가 d를 색칠하는 경우에도 비슷합니다.

div가 가장 큰 노드가 여러 개 있으면 그 중 degree가 가장 높은 노드를 색칠한다거나, degree가 4 이상인 노드만 확인하는 등의 추가 전략은, 위 그래프에서 각 노드마다 적절한 수의 노드를 추가로 붙여 주는 식으로 파훼가 가능합니다.

댓글을 작성하려면 로그인해야 합니다.