AtCoder Regular Contest 098:E - Range Minimum Queries
問題
https://atcoder.jp/contests/arc098/tasks/arc098_c
考えたこと
だとするともとの数列 をソートして連続する 個の要素の最小値をとればよいことはわかった。これはしゃくとり法とかで でできる。
選べない数を除々に決めていきたいが、これは小さい数から決めていくのがよさそう。まだ何も除いていない場合は元の数列の一番小さい数を除けば良いので一意に決まるため。
除くということを考える。これは元の数列を分割することに他ならない。分割した数列のうち、数列の要素数を とすると 個まで選ぶことができる。分割した数列から選ぶ数はよってそれぞれの分割した数列から 個を選んできて、そのうち小さい数のうち 個を選べば良い。
すべての数について分割し計算した後、最小値が解となる。
Submission #4231046 - AtCoder Regular Contest 098
どこに着目して考察するべきだったか
分割した後に、分割した数列それぞれについて、 個選べる...ということが考慮不足だった。
何がバグっていたか
以下のようにすると、元の lists に含まれる list がソートされてしまう。
for (List<Integer> list : lists) {
Collections.sort(list)
}
今回の場合は
for (List<Integer> list : lists) { tmp = new ArrayList<>(list); Collections.sort(tmp); }
とするのがよい
得た知見(典型ポイント)
- 最大値と最小値の最大化は、最大値の最小化
- 小さい数から貪欲(自由度の小さいほうから)