Codeforces #243 Div1 A. Sereja and Swaps

CF243に参加。Aをさっさと解いた後Bが解けず時間を浪費し、終盤何とかCを解いた。
Cが正解できたためひどい順位にはならなかったけどレートは微減。
http://codeforces.com/contest/425/problem/A

問題

N個の整数からなる数列Aが与えられる。
最大K回までA内の２要素のswapが可能である。
この時、Aの連続する部分列の総和を最大化せよ。

解法

愚直に実装すれば間に合う。
まず部分列の左端と右端を総当たりする(O(N^2))。
部分列に含まれるうち小さい順K個以下を、部分列の外側の大きい順K個と入れ替えて総和を求めればよい。
O(N^3*(logN + K))と結構重いが、N<=200なので200msで実行できた。

int N,K,A[10000];

void solve() {
	int f,i,j,k,l,x,y,r;
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	int ma=-1000000;
	FOR(l,N) for(r=l;r<N;r++) {
		vector<int> V1,V2;
		FOR(i,N) {
			if(i>=l && i<=r) V1.push_back(A[i]);
			else V2.push_back(A[i]);
		}
		sort(V1.begin(),V1.end());
		sort(V2.begin(),V2.end());
		FOR(i,min(min(K,(int)V1.size()),(int)V2.size())+1) {
			int t=0;
			FOR(j,V1.size()) {
				if(j<i) t+=V2[V2.size()-1-j];
				else t+=V1[j];
			}
			ma=max(ma,t);
		}
	}
	cout<<ma<<endl;
}

まとめ

これはすんなり解けてよかった。
手元の環境では最大ケースで600ms程度行ってびっくりしたんだけど、しばらく前の実行環境変更でCFの環境はだいぶ高速になったのかね。