Codeforces #616 Div1 A. Mind Control

この回もわりとポカしてるな。
http://codeforces.com/contest/1290/problem/A

問題

N要素の数列が与えられる。
これらの要素を、N人が順に1つずつ取り除くのだが、その際先頭か末尾かいずれかを取り除くことになる。

今自分はM番目に並んでいるとする。
他の人のうちK人まで、先頭と末尾どちらを取り除くか指定できるとする。
自分が取り除ける値の最大値を求めよ。

解法

自分より後の人の取り除き方を決める意味はないので、前からK人取り除こう。
先頭から確定的に取り除く人数を総当たりすると、末尾から確定的に取り除く人数も決まる。
その他の人はどちらから取り除くかわからないので、自分の手番に現れる数列の状態を全列挙し、先頭と末尾大きい方を取り除いた時の(先頭と末尾の)最大値の(各数列の状態の)最小値の(先頭から取り除く人数を総当たりしたときの)最大値を求めよう。

int T;
int N,M,K;
int A[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		K=min(K,M-1);
		FOR(i,N) cin>>A[i];
		int ma=0;
		int L,R;
		
		FOR(L,K+1) {
			int R=K-L;
			int lef=M-1-K;
			int ret=1<<30;
			FOR(x,lef+1) ret=min(ret,max(A[L+x],A[N-1-R-(lef-x)]));
			ma=max(ma,ret);
		}
		cout<<ma<<endl;
		
	}
}

まとめ

ちょっと大げさな問題名。