ARC 098 E - Range Minimum Queries
問題概要
サイズNの数列からサイズKのsubarrayを選び,subarrayのminを取り除く試行をQ回行う.
取り除いたminのうちの max - min をminimizeするように試行を行った時のminを求めよ.
1 <= N <= 2000, 1 <= a_i <= 109
解法
思考箇条書き
- 単純に小さい順に選んでいったとすると, sortして a_{Q-1} - a_0 となる.
- 選んだ数のうち A=max, B=min とすると,Aを固定したらBをmaximize, Bを固定したらAをminimizeする
- 区間minをmaximizeは難しい,ある値以下(or未満)を取ってはいけないとして取れる値のうちmaxを探す?
- minのmaxと言うと二分探索が思い浮かぶ,取る数を固定して二分探索?
- 一方で,区間minのminimizeは簡単,その値が入る区間を取ればいいだけ
- Bを固定して,Aをminimizeすることを考えるとある値未満は取ってはいけないとしてminを求めるのが良さそう
- ある値未満は取ってはいけないと言うのは, a をその値未満でsplitすればOK
- splitしたarrayを {s} とすれば, |s|<Kならそこからは取れない, |s|>=K なら |s|-K+1回取れる
- B = a_i としてみると,その値を確実に取って, a_iとa_i未満の値でsplitしたaから条件を満たすようにQ-1個取る?
- a_iとa_i未満の値 <- この議論はaが全て異なれば単純にa_i以下とできるが, そうでなければちょっとめんどい
- Bの範囲を固定するようにして, 単純に小さい順にQ個取ってくるようにしよう
- つまり, a_i以上の値を取らないといけないが,必ずしも取らなくても良いと言う縛り
- しかしどうせ小さい順に取ってくるので a_i は取ることになる.
- 各 a_i について, a_i 未満でsplitして小さい順に |s|-K+1個取ってきたもの全ての中から小さい順にQ個取る.
- sortのlogがシグマの中に入るのは気になるが,計算量は特に変わらない. O(N2 logN)
メモ
解けたい問題,という感じ