Empodia (IOI 2004)

http://wcipeg.com/problem/ioi0423

O(M^2)

관찰해야 할것은 모든 엠포디아들이 Disjoint하다는 것이다. 완전한 포함 관계는 당연히 없을 거고 겹치는 것에 대해서 얘기하자면, 두 framed interval이 [a, b] / [c, d] 로 겹쳐있다면 (a < c < b < d), [a, b] /  [b, c] / [c, d] 구간 모두 framed interval이다. 고로 [a, b]와 [c, d]는 엠포디아가 될 수 없다.

이러면 구간의 시작점을 감소시키면서 루프를 돌고, 해당 시작점에서의 empodia가 있으면, 끝점의 범위를 감소시켜나가면서 계속... 하는 M^2 알고리즘을 만들 수 있다. 조금 더 자세히 하자면, (i, j) 쌍을 찾을 때 i = N-1에서 감소 시켜 나가고, j는 i에서 증가시켜 나가는데, 만약 (i, j)가 엠포디아면 답으로 정하고, 다음 탐색 때는 끝점이 현재 i를 넘지 못하게 하는 식이다.

웃긴 건 이것만 알고 발로 M^2를 돌려도 100점이 나온다. 정해에도 M^2까지만 써져 있고.. 그러니까 M < 60000을 M^2에 풀라고 냈던 건가? 킁...

O(MlgM) / O(M)

구간의 시작점을 감소시키는 것은 똑같은데, 먼저 끝점의 하한을 잡아놓자. 끝점의 하한은 M^2에서 가지고 다니는 하한도 있고, 또한 A[i] > A[j]이며 i < j인 가장 작은 j 역시 끝점의 하한일 것이다. 이러한 점을 찾는 건 여러 방법이 있는데 스택을 써 주는 게 로그도 안 붙고 제일 깔끔하다.

이제 하한 안에 있는 점들이 엠포디아일 조건은 -

 * 1. [i, j]에 대해서 Max[i, j] <= A[j]

 * 2. [i, j]에 대해서 A[j] - A[i] == j - i

두 조건을 만족하면 되는데, 첫번째 조건을 만족시키기 위해서 처음부터 스택을 가지고 있는다. i번째 스택은 점 i에서 시작하는 증가수열을 담고 있으며, 이는 i+1번째 스택에서 쉽게 변형시킬 수 있다.

 ( 증가수열이란 말이 조금 애매하게 들릴 수 있는데 말 그대로 1번 식을 만족하는 점 j를 들고 있는다고 생각하면 된다.. 그건 쉽게 가능하다.)

두번째 조건은 std::set을 사용해 준다. 스택에 있는 점들을 똑같이 관리해주는 set을 가지고 있는다. (스택에 들어가 있으면 넣고 없으면 뺀다) 이 때 비교 기준은 A[j] - j인데, 스택에 있는 점들이면 1번 조건은 만족할 테고, A[j] - j인 점들 역시 점의 위치 순으로 정렬되어서 이쁘게 들어가 있을 것이다. 위치가 가장 작은 애를 꺼내고 하한보다 작은지 체크한 후 작으면 엠포디아.

O(M)을 달성하기 위해서는 set 대신 O(N)개의 스택을 잡으면 된다. 요상하게 메모리 터지기에 난 걍 set 썼음.