問題

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

考え方

条件の数式 $a_j \le a_i - K\ (i \lt j)$ をぐっと睨む。条件を満たす個数が大きくなる場合は $i$ になるべく大きい数を置く場合である。 $a_i$ の大きい順に左から考えていくと $1 \le a_i \le N$ なる $a_i$ について条件を満たす数列の個数は一意に決まって、それは $max(a_i-k,0)$ 個である。

よって $r=0$ になるまで $a_i$ が大きい数から順番に左から数列を構築すると条件を満たす数列が構築できる。 $r \lt 0$ になる $a_i$ の場合はスキップする。条件を満たす数列に含まれない残りの数 $a_j$ は、残りの数をソートして、左から順におけば、 $1 \le K$ より、ソート済の数列の残りの数によって条件を満たす個数は $0$ になるので、構築することができた。