티스토리 뷰

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

'공부 > Problem solving' 카테고리의 다른 글

RUN@KAIST 8/23 방학 연습 풀이  (0) 2018.01.17
RUN@KAIST 2018 겨울 1주차 연습 문제  (1) 2018.01.16
Dominator Tree  (1) 2018.01.13
2017 ICPC 팀노트 공개  (3) 2017.11.22
(팀연습) JAG Summer Camp 2014  (0) 2017.11.21
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday