ARC098 E : Range Minimum Queries(600)
作成日：2018.09.29
最終更新日：2018.09.29
問題概要
長さ$N$の数列$\{A_i\}$に対して、操作「長さ$K$の連続する部分列を選び、その中に含まれる要素で最小のものを取り除く」を$Q$回行う。
操作で取り除いた要素の最大値と最小値の差の最小値を求めよ。
制約
$1 \leq N \leq 2000$
$1 \leq K\leq N$
$1 \leq Q \leq N-K-1$
$1 \leq A_i \leq 10^9$
考え方
操作によって区間内の最小の要素を取り除くから、取り除いた要素の最小値を固定すると、その最小値未満の要素を含む区間を選ぶことができない。
このような要素を削除することで元の数列を切断した時、切断された数列$\{C_j\}_k$それぞれにおいては自由に操作を行うことができる。
取り除いた要素の最大値は小さいほうが良いから、操作を行う時は数列内で最小の要素を含むように区間を選ぶべきである。
そしてこれは、$\{C_j\}_k$それぞれにおいては常に可能である。
長さが$K$以上である限り操作を行えるから、各$\{C_j\}_k$において大きいものから$(K-1)$個の要素を取り除いた時に残る要素の集合$S$を考え、$S$内の要素を小さいものから$Q$個が取り除かれるように操作を行うのが固定した最小値において最善である。
最小値を固定するごとに、$S$を用意して小さいものから$Q$個とるのは$O(N \: log \: N)$でできる。
よって最小値として$A_i$をすべて試すことで、答えが$O(N^2 \: log \: N)$で求めることができる。
これは十分高速である。
ソースコード
マクロ等はこちら
int N,K,Q;
int A[2010];
int main(){
cin >> N >> K >> Q;
repp(i,0,N) cin >> A[i];
int ans = 1e9;
repp(i,0,N){
vector<int> V,S;
repp(j,0,N){
if(A[j] < A[i]){
sort(V.begin(),V.end());
repm(k,(int)V.size()-K,-1) S.push_back(V[k]);
V.clear();
} else {
V.push_back(A[j]);
}
}
sort(V.begin(),V.end());
repm(k,V.size()-K,-1) S.push_back(V[k]);
if((int)S.size() >= Q){
sort(S.begin(),S.end());
ans = min(ans,S[Q-1]-S[0]);
}
}
cout << ans << endl;
return 0;
}解法まとめ
各$A_i$において、元の数列で$A_i$以上の要素が連続する箇所$V_j$をすべてとる。
各$V_j$の要素のうち大きいものから$(K-1)$個取り除いて残った要素をすべて$S$に入れる。(10-20行)
$S$内で最小の要素と$Q$番目に小さい要素の差を求める。
すべての$A_i$におけるこの差の最小値が答えである。(7,21-24,26行)