Sails (IOI 2007)

핵어렵다 ㅎㅎ

https://www.acmicpc.net/problem/5474

1. Greedy  - O(NHlgH)

그리디 전략을 설명하기 전에 사실 돛대의 순서들이 문제에 전혀 상관이 없다는 사실을 알아야 한다. 때문에 돛들을 편한대로 정렬한 다음에 쓰면 된다.

그리디 전략은 다음과 같다. 돛대라는 말은 어감이 짜증나니(?) 막대라는 말로 대신하겠다.

" 막대들을 길이가 증가하는 순서대로 정렬한 후, 각 막대에 대해서 H개의 돛들을 꽂을 수 있는 열 중 가장 꽃혀있는 돛이 적은 열에 꽃는다. 이를 모든 돛에 대해서 반복한다. 이후 열에 꽃혀있는 돛의 개수가 n개일 경우 n * (n-1) / 2를 각 열에 대해서 더한다."

딱 봐도 될거같은 이 그리디 전략은 실제로 된다. (^^;) 왜 되는지는 나도 모르니 패스 ㅎㅎ

이 를 구현하려면 각 열들을 vector 등에 넣고 처리한 후, 각 막대를 처리할 때마다 vector를 정렬한 후 작은 곳에서부터 하나씩 더해가면 된다. 길이가 증가할때마다 vector에 0을 넣는 걸 잊지 말자. 이 방법의 시간 복잡도는 O(NHlgH) 이다.

2. Advanced Implementation - O(NlgN + NH)

정 렬을 하는 과정에서 사실 약간의 낭비를 느낄 수 있는데, 순서대로 1을 더했기 때문에 실제로는 순서가 생각보다 많이 안 꼬였다는 점을 감안해야 한다. 이 부분을 적절히 처리해나가면서 정렬된 배열을 유지하면 O(NH)에 문제를 풀 수 있다.

정확한 과정을 설명하자면

현재 열의 상태가 이렇다고 하자 :  765333322211110000

가장 꽃혀있는 돛이 적은 열 6개를 골라 칠하는게 이번의 쿼리이다 : 765333322211221111

이 때 칠한 6개 주변에서만 순서가 뒤바뀌는 일이 생기고 그 외에는 순서가 뒤바뀌지 않는다. 때문에 이 부분만 적절히 선형 시간에 처리하는 것으로 O(NH)에 구현할 수 있다. 6개를 칠한다고 할 때, 6번째 원소 주변에서 1과 2의 지속 시간을 체크한 후 그에 따라 쿼리를 처리한다.. 정도로 해석하면 된다.

3. Binary Search Tree - O(NlgN + (N+H)lgH)

저 아이디어를 그대로 세그먼트 트리등으로 구현하면 트리의 구간 갱신과 구간 가산 연산을 동시에 지원해야 하는데 되는지도 잘 모르겠고, 되더라도 상당히 코딩하기 힘들다. 그런데 저 문제에서는 원소가 비증가한다는 조건이 있기 때문에 이 조건을 잘 사용하면 Binary Search Tree를 사용하면 된다.

먼저 돛을 변홧값 배열을 사용해서 저장하면 ...[-1][-3]....[-1]..[-2] 와 같은 형태로 저장이 되어 있음을 알 수 있다. 편의상 왼쪽 순서로 봤으며 변홧값 배열에는 음수항만이 있음을 알 수 있다. 이 중 가장 왼쪽에만 돛을 달기 때문에 [+1] 과 [-1] 을 칠해줌으로써 갱신을 해준다는 것을 알 수 있다. 때문에 배열 내부의 실제 값 변화 없이 [+1] 을 적절히 처리해서 더하지 않는 방법을 사용해야 한다.

앞에서 구현시 6번째 원소 주변에서 1과 2의 지속 시간을 체크하면서 문제를 풀었기 때문에 이번에도 비슷한 방법으로 이를 처리한다. 오른쪽에서 [+1]과 매칭되는 것 중 가장 가까운 것을 고른 후, 그 부분을 변홧값 배열 상에서 적절한 위치에 옮겨놓은 후 같이 제거해버리는 방식이다.

예를 들어 설명하자면

765333322211221111

과 같은 배열이 있을 때 6에서 매칭되는 가장 가까운 -1은 22[]1111 쪽의 -1일 것이다. (구현 시에는 lower_bound로 쉽게 구할 수 있다.) 이를 쌍으로 해놓고 해당 위치에 있는 -1을 지운다. (-1이 아닐 경우에는 그냥 1을 증가시킨 후 유지한다.) 이 때 매칭되는 부분의 거리인 2를 저장해 놓는다.

765333322211111111 -> match = 2

앞 에 6이 있던 부분에서 가장 가까운 -1 (왼쪽) 은 3222[]11111 부분일 것이다. 이 부분에 아까 매칭된 거리인 2를 붙여넣으면 된다. 이 역시 lower_bound로 쉽게 구할 수 있으며 구한 이후 해당 부분의 -1을 지우고 그 위치에 +2에 -1을 삽입하면 된다. (아까와 같이 -1이 아닐 경우에는 그냥 1을 증가시킨 후 유지한다.)

765333322222111111

변환이 완성되었다.

이러한 과정을 반복한 후 변홧값 배열을 다루는 일반적인 방법으로 계산을 하면 위에 서술한 시간복잡도가 나온다. 코드는 50줄 가량으로 길지 않은 편이다.

여담으로 스택을 사용해서 선형 시간에 한번에 해버리는 풀이도 있다고 한다 (!!!) 코드도 엄청 짧은 풀이로 관심이 있다면 찾아보길 바란다.