問題

長さ $N$ の数列[A_1, \cdots, A__N]から $K$ 個の要素を選んで部分数列を作る。要素を選ぶときは、要素ごとに $D$ 以上開ける必要がある。辞書順で最小の数列を求める。

考察

$D(K-1) + 1 \gt N$ のとき、部分列を作ることはできない。以下、 $D(K-1) + 1 \leq N$ を仮定する。

同じ数字が複数あり、どちらも採用できるとき、なるべく先の方を採用した方がいい。

1文字目は、 $A_1, \cdots A_{N-D(K-1)}$ から選ぶ必要があり、この中で最小の文字にするとよい。また、最小の文字が複数ある場合はもっとも先にある方を選ぶ。 $k$ 文字目の引数を $i_k$ とすると、2以上の $k$ について、 $k$ 文字目は $A_{i_{k-1}}, \cdots A_{N-D(K-k)}$ の最小の文字のうちもっとも先のものを貪欲に選べばよい。