수열 매끄럽게 만들기

답을 $D$ 이하로 만들 수 있는지 판정하는 문제를 생각하자.

값을 바꾸지 않고 남겨 둘 위치들을 $i_1<i_2<\cdots<i_m$이라 하자. 연속한 두 위치 $i<j$를 모두 남겨 두려면

$$|A_i-A_j| \le D(j-i)$$

가 필요하다. 이 조건은 충분하기도 하다. 두 끝값의 차이가 $D(j-i)$ 이하이면, 그 사이의 바뀐 원소들을 한 칸마다 최대 $D$만큼 움직이도록 정수로 채울 수 있다. 맨 앞과 맨 뒤의 바뀐 구간도 항상 채울 수 있다.

따라서 적어도 $N-K$개의 원래 값을 남길 수 있는지를 확인하면 된다.

서브태스크 4: $N\le2000$

$dp_i$를 $i$번 위치를 마지막으로 남겨 둘 때, 남길 수 있는 원래 값의 최대 개수라고 하자. 앞의 위치 $j<i$와 함께 남길 수 있는 조건을 직접 확인하면

$$dp_i=1+\max_{\substack{1\le j<i\\|A_i-A_j|\le D(i-j)}}dp_j$$

이다. 조건을 만족하는 $j$가 없으면 최댓값을 $0$으로 둔다.

$i=1,2,\ldots,N$ 순서로 계산하여 $\max_i dp_i\ge N-K$인지 확인한다. 한 번의 판정은 이고, 이를 이분 탐색에 사용하면 시간 복잡도는 , 공간 복잡도는 이다.

각 위치 $i$에 대해

$$X_i=A_i-Di,\qquad Y_i=A_i+Di$$

를 정의한다. $i<j$에 대해 위 조건은 다음 두 부등식과 동치이다.

$$X_i\ge X_j,\qquad Y_i\le Y_j$$

점 $(X_i,Y_i)$를 $X_i$가 큰 순서로 정렬하고, 가 같으면 가 작은 순서로 정렬한다. 이 순서에서 의 최장 비감소 부분수열 길이를 이라 하자. 그러면 은 동시에 남겨 둘 수 있는 원래 원소의 최대 개수와 같다.

$D>0$이면 $Y_i-X_i=2Di$이므로 위의 두 좌표 조건을 만족하는 두 점의 순서는 원래 인덱스 순서와도 일치한다. 이면 이고, 비감소 부분수열에는 같은 값만 함께 들어갈 수 있으므로 역시 올바르다.

따라서 $L\ge N-K$이면 $D$가 가능하고, 그렇지 않으면 불가능하다. 최장 비감소 부분수열은 upper_bound를 이용해 $O(N\log N)$에 구할 수 있다.

가능 여부는 $D$가 커질수록 단조롭게 참이 된다. $0$부터 원래 수열의 최대 인접 차이까지 이분 탐색한다. 전체 시간 복잡도는 $O(N\log N\log C)$이고, $C\le 2\cdot 10^9$이다. 메모리 복잡도는 이다.

Solution written by GPT6