Careful Deletion

마지막 원소를 고정했을 때의 비용

마지막으로 지우는 원소의 원래 위치를 $k$라고 하자. $k$보다 왼쪽의 원소는 반드시 맨 앞에서, 오른쪽의 원소는 반드시 맨 뒤에서 지워진다. 따라서 $k$를 마지막까지 남길 수 있다면 비용은 다음과 같이 결정된다.

$$C(k)=\sum_{i<k}L_{P_i}+\sum_{i>k}R_{P_i}+\min(L_{P_k},R_{P_k}).$$

삭제 순서 교환

현재 삭제 가능한 양 끝 원소 중 하나를 $x$라고 하자. $x$를 지우지 않는 동안 $x$는 계속 같은 끝에 있고 최솟값 또는 최댓값이다. 완전한 삭제 순서에서 $x$의 삭제를 맨 앞으로 옮겨도 나머지 삭제는 유효하다. 원소를 먼저 없애도 다른 원소의 최솟값·최댓값 성질은 깨지지 않으며, 반대쪽 끝에서 수행하던 삭제도 그대로 가능하다. 마지막 원소의 삭제 방향만 바뀔 수 있으므로 이 주장은 가능 여부에만 사용한다.

따라서 현재 삭제 가능한 어느 쪽을 먼저 지워도 완전 삭제 가능 여부는 같다. 또한 마지막 위치 $k$가 $x$의 위치와 다르면, $x$를 먼저 지워도 $k$를 마지막으로 남길 수 있다.

가능한 마지막 위치는 연속한 구간이다

남은 길이에 대한 귀납법을 사용한다. 길이 $1$이면 자명하다. 삭제 가능한 끝이 없으면 불가능하고, 한쪽만 가능하면 그 원소를 지운 상태로 귀결된다.

양쪽 끝이 모두 가능하면 어느 쪽을 먼저 지우는지에 따라 두 상태로 나뉜다. 길이 $2$에서는 두 위치 모두 마지막 위치가 될 수 있다. 길이가 $3$ 이상이고 완전 삭제가 가능하다면, 교환 성질에 의해 양쪽 끝을 먼저 지운 가운데 상태도 완전 삭제가 가능하다. 가운데 상태의 가능한 마지막 위치는 두 자식 상태 모두에서 가능하다. 귀납 가정으로 두 자식의 가능한 마지막 위치 집합은 구간이며, 공통 원소가 있으므로 합집합도 구간이다.

구간의 양 끝 구하기

삭제할 수 있을 때마다 왼쪽을 우선하여 삭제한다. 왼쪽 끝보다 오른쪽에 있는 어떤 가능한 마지막 위치도 이 선택으로 사라지지 않는다. 왼쪽을 지울 수 없다면 오른쪽 삭제가 강제된다. 따라서 마지막에 남는 위치는 가능한 마지막 위치 중 가장 오른쪽이다. 반대로 오른쪽을 우선하면 가장 왼쪽 위치를 얻는다.

시뮬레이션 도중 두 끝 모두 지울 수 없다면 정답은 -1이다. 그렇지 않으면 두 시뮬레이션으로 얻은 위치 사이의 모든 $k$에 대해 $C(k)$의 최솟값을 구한다.

남은 위치는 항상 구간이고, 남은 값도 항상 연속한 정수 구간이다. 위치의 양 끝과 값의 최솟값·최댓값을 각각 유지하면 각 삭제를 $O(1)$에 처리한다. 비용은 왼쪽 누적 합과 오른쪽 누적 합으로 계산한다. 총 시간 복잡도는 $O(N)$, 공간 복잡도는 $O(N)$이다.

비용 합은 최대 $N\cdot10^9\leq2\cdot10^{14}$이므로 64비트 정수형을 사용한다.

함께 제공한 단순 풀이는 각 위치 구간에서 양 끝 삭제를 모두 고려하는 구간 DP이다. 길이 순서로 계산하고 이전 길이의 결과만 유지하여 $O(N^2)$ 시간, $O(N)$ 공간을 사용한다.

Solution written by GPT