AtCoder ARC #098 : E - Range Minimum Queries

一部の時間しか参加しなかったので微妙な順位。
https://beta.atcoder.jp/contests/arc098/tasks/arc098_c

問題

N個の整数列がある。
ここから長さKの部分列を選び、その最小値を取り除く、という作業をQ回繰り返す。
取り除いた値の最大値と最小値の差の最小値を求めよ。

解法

取り除く値の最小値Xを総当たりしよう。
Xが下限ということは、元の整数列からX未満の要素が取り除けない。
よって取り除けるのは、元の数列をX未満の値で分割したとき、長さK以上の部分列があれば、そこからいくつか取り除くことができる。
取り除ける全候補から、実際に取り除けるものを小さい順にQ個選べばよい。

int N,K,Q;
int A[2020];
int mi=1<<30;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>Q;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N) {
		vector<int> P;
		vector<int> V;
		FOR(j,N) {
			if(A[j]<A[i]) {
				if(V.size()>=K) {
					sort(ALL(V));
					FOR(x,V.size()-K+1) P.push_back(V[x]);
				}
				V.clear();
			}
			else {
				V.push_back(A[j]);
			}
		}
		if(V.size()>=K) {
			sort(ALL(V));
			FOR(x,V.size()-K+1) P.push_back(V[x]);
		}
		if(P.size()<Q) continue;
		sort(ALL(P));
		mi=min(mi,P[Q-1]-P[0]);
	}
	cout<<mi<<endl;
	
}

まとめ

これは600ptだしそこまで難しくもないかな。