問題

考えたこと

$K = 1$ だとするともとの数列 $\{A_N\}$ をソートして連続する $Q$ 個の要素の最小値をとればよいことはわかった。これはしゃくとり法とかで $O(N)$ でできる。

選べない数を除々に決めていきたいが、これは小さい数から決めていくのがよさそう。まだ何も除いていない場合は元の数列の一番小さい数を除けば良いので一意に決まるため。

除くということを考える。これは元の数列を分割することに他ならない。分割した数列のうち、数列の要素数を $m$ とすると $m-k+1$ 個まで選ぶことができる。分割した数列から選ぶ数はよってそれぞれの分割した数列から $m-k+1$ 個を選んできて、そのうち小さい数のうち $Q$ 個を選べば良い。

すべての数について分割し計算した後、最小値が解となる。

分割した後に、分割した数列それぞれについて、 $m-k+1$ 個選べる...ということが考慮不足だった。

以下のようにすると、元の lists に含まれる list がソートされてしまう。

for (List<Integer> list : lists) {
    Collections.sort(list)
}

今回の場合は

for (List<Integer> list : lists) {
    tmp = new ArrayList<>(list);
    Collections.sort(tmp);
}

とするのがよい