IOI 2012 tournament

이번 선발고사에서 공동 4등...을 해버리며 슈뢰딩거의 국대가 되어버렸다. 국대가 5명일 수는 없으니 이제 또다른 방법으로 국가대표를 선별해야할텐데, 그래서 PS에 인생을 올인 박는 것이 별로 나쁘지 않은 선택이 되는 상황이 되었다. 그리고 학교에 오니 재밌는 할거리가 PS하기밖에 없어서 당분간 PS에 집중하려고 한다. 그래서 일단 집고 풀어본 문제가 IOI 2012 tournament이다.

문제의 내용은 oj.uz/problem/view/IOI12_tournament를 참고하자.

 

여기서 첫번째로 해야 될 관찰은 마지막 기사의 위치에 따라 [Si,Ei]가 뜻하는 바가 막 변할 것 같지만 그렇지 않다는 것이다. '이긴 기사'가 '패배한 기사'들까지 모두를 대표하고 있다고 생각하자. 이렇게 생각하면 [Si,Ei]에 속하는 기사들이 대표하고 있는 기사들은 항상 같다는 것을 쉽게 알 수 있다. 그러므로 모든 [Si,Ei]가 길이 N의 구간에서 어느 부분에 속하는지 알아두고, 그걸 [si,ei]라 하자. 이는 세그먼트 트리에서 kth seg 테크닉을 잘 이용하면 쉽게 찾을 수 있다.

두번째로 해야 할 관찰이자 가장 중요한 관찰은 구간 [si,ei]들은 서로 교차하지 않고 서로 포함하거나 포함되는 관계이다. i<j인 정수 i,j에 대해 구간 [si,ei]와 [sj,ej]가 교차한다고 하자. 하지만 이미 [si,ei]에 속하는 기사들은 그에 속하는 어떤 기사에게 패배당해 그 기사가 이 구간을 대표하게 되었을 것이다. 그런데 [sj,ej]가 [si,ei]와 교차한다면 [sj,ej]가 [si,ei]의 일부분만을 포함해야 하는데 이미 한 기사가 [si,ei]를 모두 대표하므로 전부 포함하거나 포함하지 않거나 둘 중 하나로 모순이다.

이제 우리는 [si,ei]의 구간들로 트리를 구성할 수 있다. 그러면 문제는 다음과 같이 바뀐다. '어떤 리프 정점에 마지막 기사를 배치해서, 그 리프 정점과 그 정점의 조상 중 정점이 나타내는 구간의 최댓값이 R보다 큰 가장 낮은 정점과의 거리를 최소화하여라.' 이 문제는 이렇게 해결할 수 있다. 우선 0번 정점에 마지막 기사를, i+1번째 정점에 i번째 기사를 배치한 이후 구간 트리를 구성하자. 그리고 dfs 넘버링을 하고 실력이 R보다 큰 기사에 대해서 그 위치에 1을 업데이트해준다. 그리고 어떤 정점이 나타내는 구간의 최댓값이 R보다 큰지 확인하려면 단순하게 그 정점의 서브트리의 값들의 합이 0이 아닌지 확인하면 된다. 이러면 이분탐색을 수행하여 O(log^2N)의 시간복잡도로 최대 승리 횟수를 알 수 있다. 그리고 이제 마지막 기사를 계속 다음 순서로 옮겨주자. 단순하게 만약 이 기사가 옮겨지면서 이전 순서로 옮겨지게 될 기사의 실력이 R보다 크면 원래 그 위치에 1을 업데이트했던 걸 취소해주고 그 이전 위치에 1을 업데이트해주고 이전에 했던 과정을 반복해주면 된다. 최종 시간복잡도는 O(Nlog^2N)이다.

 

코드 : oj.uz/submission/372921