水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 098 : E - Range Minimum Queries

  • 問題

E - Range Minimum Queries

長さ N の数列 A から「長さ K の連続する部分列を1つ選び、その中の最小値を数列から取り除く」動作を Q 回行う。Q 回で取り除いた Q 個の数値の最大値と最小値の差の最小値を求める問題。

 

  • 解法

最小値を固定させると、まず、固定させた最小値より小さい要素は取ってはいけないので、固定させた最小値より小さい要素を含まない部分列を列挙する。その後、それぞれの部分列をソートし、その中で最大値として考えられるものを全て列挙し、最大値の候補をソートし Q 番目に小さいものを最大値とする。最初に決める最小値を A_0 ~ A_N まで試した中で、最大値と最小値の差が一番小さいものを出力すればよい。最大値を固定させてもできる。

 

  • 解答

Submission #2716762 - AtCoder Regular Contest 098

f:id:babcs2035:20180623175117p:plain