ICPC 2015 Tsukuba K. Min-Max Distance Game

먼저 “Alice가 답을 $T$ 이상으로 하는 게임을 진행할 수 있는가, 없는가?” 라는 변형된 문제를 풀어보자. 변형된 문제를 빠른 시간 안에 풀 수 있다면, 이분 탐색을 통해서 Alice가 진행할 수 있는 게임 중 $T$가 가장 큰 것을 찾을 수 있고, 이것이 Alice가 얻을 수 있는 최댓값이기 때문이다.

이후부터는 문제를 그래프로 변형해서 해결한다. $\mathrm{\mid }{A}_u-A_v\mathrm{\mid }<T$ 인 모든 $1 \leq u < v \leq n$에 대해서 간선을 이어주자. $n-2$번의 턴 동안 정점을 제거하며, 남은 두 정점에 에지가 없으면 Alice가 승리하고, 아니면 Bob이 승리한다.

이후 상황에 대해서 몇가지 케이스를 생각해 보자. 첫 번째로, 만약에 $1+\lceil n\mathrm{/}2\rceil$크기의 클리크가 있다면, Bob은 클리크 밖에 있는 정점만을 지우면서 이길 수 있다. Alice가 게임에서 지울 수 있는 정점은 많아야 $\lceil n / 2 \rceil - 1$개이고, 결국 클리크에 있는 두 개 이상의 정점이 남기 때문이다.

두 번째로, 그래프에 $\lfloor n/2 \rfloor -1$ 크기의 Vertex Cover가 있다면, Alice는 Vertex Cover 안에 있는 정점만 다 지우면 에지들을 완전히 제거할 수 있다. Bob이 무엇을 하든 상관없이 Alice는 무조건 게임에서 승리할 수 있다.

그 외의 상황에서는 어떤 일이 벌어질까? 일단, 그래프에 크기 $1+\lceil n\mathrm{/}2\rceil$ 의 클리크가 있으면 Vertex Cover의 크기는 최소 $\lceil n/2 \rceil$이기 때문에, 두 경우가 동시에 성립하지는 않는다. 두 경우가 모두 성립하지 않는 경우에는, 항상 마지막 턴을 진행한 사람이 승리한다. 이는 케이스를 나눈 후 수학적 귀납법을 사용해서 보일 수 있다.

Case 1. Alice가 마지막 턴을 진행할 경우

다음과 같은 명제를 증명한다 :

모든 $n\ge 3$에 대해서, 주어진 그래프에서의 최대 클리크의 크기가 $\lceil n/2 \rceil$이하이고 Alice가 마지막 턴을 진행할 경우, Alice는 항상 이길 수 있다.

• (base case) $n = 3$일 경우에는 클리크의 크기가 2 이하이다. Alice가 2번째 정점을 지우면 무조건 승리한다. (1번 정점과 3번 정점만 연결된 경우는 존재하지 않는다. 그래프의 성질에 의해서, $v$와 $w$사이에 에지가 있으면 $[v, v+1, \cdots, w]$ 사이에 클리크가 존재함을 기억하자.)

• (inductive case) $n > 3$이고 짝수인 경우에는, Bob이 정점을 지운다. $\lceil n/2 \rceil = \lceil (n-1)/2 \rceil$ 이기 때문에 어떤 정점을 지우더라도 귀납 가정을 만족해서 Alice가 이긴다.

  $n>3$이고 홀수인 경우에는, Alice가 이번 턴을 진행한다. 만약에 최대 클리크의 크기가 $\lceil n/2 \rceil$인 경우, 중간에 있는 정점, 즉 $\lceil n/2 \rceil$ 번 정점은 이 클리크에 무조건 속함을 알 수 있다. (다시 한번, $v$와 $w$ 사이에 에지가 있으면 $[v, v+1, \cdots, w]$사이에 클리크가 존재함을 기억하자.) 고로 이 정점을 지우면, 귀납 가정을 만족하게 된다. 최대 클리크가 $\lceil n/2 \rceil$ 미만인 경우 무엇을 지워도 자명히 귀납 가정을 만족한다.

Case 2. Bob이 마지막 턴을 진행할 경우

조금 더 복잡한데 아무튼 비슷하다. 이번에는 다음과 같은 명제를 증명한다 :

모든 $n \geq 3$에 대해서, 주어진 그래프에서의 최소 정점 덮개 (Minimum Vertex Cover) 의 크기가 $\lfloor n/2 \rfloor$ 이상이고 Bob이 마지막 턴을 진행할 경우, Bob이 항상 이길 수 있다.

• (base case) $n = 3$일 경우에는, Vertex Cover가 크기 1 이상이니 에지가 하나 이상 존재한다. 이 에지를 피해서 정점을 지우면 항상 이길 수 있다.

• (inductive case) $n > 3$이고 짝수인 경우에는, Alice가 정점을 지운다. $\lfloor n/2 \rfloor - 1 = \lfloor (n-1)/2 \rfloor$기 때문에, 어떤 정점을 지우더라도 귀납 가정을 만족해서 Bob이 이긴다.

  $n > 3$이고 홀수인 경우에는, Bob이 이번 턴을 진행한다. 만약의 최소 정점 덮개의 크기가 $\lfloor n/2 \rfloor$초과일 경우, 어떤 정점을 지우더라도 귀납 가정을 만족한다. 최소 정점 덮개의 크기가 $\lfloor n/2 \rfloor$일 경우를 생각해 보자. 어떠한 최소 정점 덮개 $C$에 대해서, $C$에 속하는 정점의 개수($\lfloor n/2 \rfloor$)보다 그렇지 않은 정점의 개수 ($\lfloor n/2 \rfloor+1$)가 더 많은 상황이다. 고로, $C$에 속하는 정점의 개수보다 그렇지 않은 정점의 개수가 더 많은 연결 컴포넌트가, 그래프에 존재할 것이다. 그 컴포넌트를 생각해 보자.

  문제에서 주어지는 그래프의 특성 상, 컴포넌트에 속하는 정점을 $A_i$ 순으로 이으면 해밀턴 경로를 만들 수 있다. 최소한 이 경로는 덮어야 하기 때문에, 컴포넌트의 크기가 $2k$이면 자명히 최소 정점 덮개의 크기가 $k$ 이상이다. 고로 우리가 생각하는 컴포넌트는 크기가 $2k+1$이며 최소 정점 덮개의 크기가 $k$임을 알 수 있다. 경로 상의 끝 점 중 하나를 제거하면, 컴포넌트는 여전히 연결되어 있고, 컴포넌트의 크기는 $2k$가 되며, 최소 정점 덮개의 크기는 $k$로 유지된다. Bob이 이 정점을 지우면 귀납 가정을 유지할 수 있어서, Bob이 이긴다.

문제에서 주어진 그래프는 에지를 굉장히 특별한 방법으로 잇는다. (이러한 그래프를 Unit Interval Graph라 한다) Two pointers를 사용해서 $A_i - A_j \geq T$ 를 만족하는 가장 큰 $j$를 전처리해두자. 이 테이블을 사용해서 Maximum Clique를 쉽게 찾을 수 있고, 이 테이블에 동적 계획법 내지는 그리디를 사용하여 최소 정점 덮개를 찾을 수 있다.