主食は米

主に競プロ備忘録

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)

メモ

解けたい問題,という感じ

コード