자력솔 루비라고 주장할수도 있었는데, 무심코 본 '이분탐색' 태그가 너무 크리티컬한 힌트였기에 완전 자력솔이라고 주장은 못하겠다..
얼핏보기에는 알려진 풀이랑 내 풀이가 상당히 다른데, 우선 내 풀이를 설명한다.
앨리스가 선공이고 n이 홀수인 경우는, 생각보다 간단하게 정리된다.
앨리스는 (n-1)/2 개의 돌을 제거하게 되고, 밥은 (n-3)/2 개의 돌을 제거하게 된다. 이리저리 생각해보면 앨리스는 항상 남은 돌중 가장 가운데에 있는 돌을 제거하는 그리디한 전략이 최선이고, 밥은 양쪽 끝에 있는 두개의 돌중 하나를 제거하는 전략이 최선이 된다. 둘다 이렇게 하게되면 마지막에 남는 두개의 돌은, 처음에 간격이 (n-1)/2 만큼 떨어져 있던 돌이 된다. 이러한 돌들중 어느것이 남게 되는지를 결정하는 것은 밥의 선택에 따른다. 그래서 최종적으로 얻게되는 점수는 m=(n+1)/2 이라고 할때 min(x[m]-x[0], x[m+1]-x[1], …, x[n-1]-x[n-m-1]) 이 된다
증명은 엄밀하게 안해봤지만.. 앨리스에게는 저것보다 높은 점수를 얻을수 있는 전략이 없는것 같다. 그리고 앨리스가 이 전략을 사용할때 밥은 더 간격이 작은 돌을 남기게 하는것은 불가능하므로, 저 간격의 돌들중 가장 낮은 점수를 갖는 돌들을 남기도록 만드는 전략이 가능한 최선의 전략이 된다.
사실 처음에 이 상태만 먼저 생각해보고 루비답지 않게 너무 쉽게 정리되어서 당황했다. 그때는 n이 짝수인 경우도 비슷한 난이도로 처리될줄 알았기 때문인데.. 사실 진짜 문제는 n이 짝수일때였다;
앨리스가 선공이고 n이 짝수인 경우는, 이전보다 많이 복잡하다. 막턴이 밥에게 돌아가는데, 이것으로 인해 얻게되는 점수가 확 낮아진다. 정확한 점수를 구하는 것은 쉽지 않은데, 이분탐색으로 답을 구하는 전략을 생각해볼수 있다.
사실 게임이론 문제를 100문제 이상 풀어봤지만, 이분탐색으로 답을 구해야 하는 문제는 이 문제가 처음이었다
게임에서 t점 이상을 얻을수 있는 전략이 있을지를 결정하는 함수를 만들어보자. n이 짝수일때에는, 앨리스와 밥이 (n/2)-1개의 돌을 제거하게 되는데, 만약 앨리스 혼자서 (n/2)-1개의 돌을 제거해서 남겨진 돌들이 모두 t 이상의 거리를 두고 떨어져있게 만들수 있다면, 밥이 어떻게 돌을 제거했든간에 t 이상의 거리를 두는 돌들이 마지막에 남게 된다.
역이 성립하는지는 좀 어렵다. 만약 앨리스 혼자서 (n/2)-1개의 돌을 제거했을때 t미만의 거리를 갖는 돌 두개가 존재하게 된다면, 밥이 그 돌들만 남기고 나머지를 제거하면 점수가 t미만이 되는것은 당연하다. 그러나 앨리스가 먼저 돌을 모두 제거한 다음 밥이 돌을 제거하는 것이 아니라, 번갈아가면서 제거하는것이다 보니, 밥이 정확히 저 돌만 남기고 제거하는 것이 가능한지는 느낌적으로는 될거 같은데 정확한 증명은 잘 안된다..
그래서 그냥 믿음을 갖고 제출해서 proof by AC에 성공하기는 했다.
x개의 돌을 제거해서 남겨진 돌들이 모두 t이상의 거리를 두고 떨어져있게 만들수 있는지는, 그리디하게 O(n)에 확인 가능하다. 이 자체는 파라메트릭 서치의 기본 문제로 많이 등장하는 유형이다
이제, 밥이 선공인 경우를 처리해야 하긴 하는데, 앨리스가 선공인 경우와 달라지지 않는다. n이 짝수일때는 앨리스가 막타를 치게 되므로, 똑같이 min(x[m]-x[0], x[m+1]-x[1], …, x[n-1]-x[n-m-1]) 으로 계산되고, n이 홀수일때는 밥이 막타를 치므로, 똑같이 앨리스가 x개를 제거해서 t이상을 만들수 있는 가장 큰 t값을 이분탐색으로 찾는다.
앨리스가 막타일때는 O(n)에, 밥이 막타일때는 O(n*logm) (m = x[n]-x[0]) 에 계산 가능하다
이렇게 풀고 나서 찾아본 다른 풀이는 많이 복잡해보였다.
하지만 뜯어보면 결국 비슷해지는데.. 저 풀이와의 가장 큰 차이는 앨리스가 막타를 치는 상황에서 그리디한 전략으로 계산하는 방법이 생략되어있다는 것이다.
저 풀이에서는 앨리스가 확실히 t이상을 만들수 있는 경우는, m크기의 버텍스커버가 있어서 앨리스가 그 m개를 지워서 에지들을 모두 제거할수 있는 경우라고 설명하고 있다. 그래프로 생각하지 않고 핵심만 찾으면, 결국 앨리스 혼자서 자력으로 간격이 t이하인 돌 페어를 모두 없앨수 있는 경우이고, 이것은 위에서 단순하게 설명한 결정함수가 찾는 것과 동일하다
그리고 저 풀이를 따르면, 버텍스 커버 조건을 만족하지 않더라도 큰 클리크가 존재하지 않으면서 앨리스가 마지막 턴을 하게 된다면, t이상을 만들수 있다고 한다. 하지만, 내경우는 앨리스가 마지막턴인 경우는 아예 다른 방법으로 풀고 있으므로, 이 조건은 신경쓰지 않아도 된다.
결국 앨리스가 마지막턴을 갖는 경우만 고려하게 된다면, 결정함수를 복잡하게 그래프에서의 최대 클리크/버텍스 커버를 이용해서 계산하지 않아도 간단한 그리디로 체크해도 동일한 결과를 얻을수 있다. 물론 구현이 아니라 정확한 증명이 목적이라면 그래프 모델링이 효과적일지도 모르겠다.