数列をなめらかに

答えを $D$ 以下にできるかを判定することを考える。

元の値を変更せずに残す位置を $i_1<i_2<\cdots<i_m$ とする。連続する 2 つの残す位置が $i<j$ なら、

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

が必要である。この条件は十分でもある。両端の値の差が $D(j-i)$ 以下なら、その間の変更する要素を、1 ステップごとの差が高々 $D$ になるように整数で埋められる。先頭側と末尾側の変更区間も常に埋められる。

よって、元の値を少なくとも $N-K$ 個残せるかを判定すればよい。

サブタスク 4: $N\le2000$

$dp_i$ を、位置 $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$ かどうかを確認する。1 回の判定は であり、二分探索と組み合わせると時間計算量は 、空間計算量は となる。

各位置 $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$ なので、2 つの座標条件を満たす点の順序は元の添字順序とも一致する。 のときは であり、 の降順に並べた後の非減少部分列に同時に入れる異なる位置は同じ値を持つ場合だけなので、やはり正しい。

したがって $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