kmjp's blog

競技プログラミング参加記です

Codeforces #253 Div1 C. Artem and Array

終わってみるとコードは短い問題。
http://codeforces.com/contest/442/problem/C

問題

N要素の数列A[i]が与えられる。
ここから、要素を1個ずつN回抜き出すことを考える。
要素を1個抜き出すと、前後の要素のうち小さい方の数値分、スコアが増える。
なお、数列の両端を抜き出す場合はスコアは増えない。

抜き出す順を最適化し、スコアを最大化せよ。

解法

数列の要素が A[i] => A[i+1] <= A[i+2]と下に凸になっている箇所を考える。
この場合、A[i+1]を最後に取り除くと、A[i]やA[i+2]を取り除いて得られるスコアはmin(A[i-1],A[i+1])やmin(A[i+1],A[i+3])である。
一方、A[i+1]を先に取り除くと、A[i]やA[i+2]を取り除いて得られるスコアはmin(A[i-1],A[i+2])やmin(A[i],A[i+3])であり、こちらの方が多い。

よって数列A[i]を端から見ていって、A[i] => A[i+1] <= A[i+2]となっている箇所があればA[i+1]を取り除く、ということを行う。
すると、残る数列B[i]はB[0] <= B[1] <= ... <= B[p-1] <= B[p] >= B[p+1] >= ... >= B[q-1]と上に凸な形になる。
個の状態で数値の大きい順に取り除くと、B[0]~B[q-1]のうち最大値2個を除いた要素の分スコアに入る。

上記処理はA[i]で下に凸な箇所を探すのにO(N)、B[i]の最大値2個を探すのにO(N)ないしO(N*logN)かかる。

int N;
vector<int> V;

void solve() {
	int f,i,j,k,l,x,y;
	
	ll ret=0;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		while(V.size()>=2 && V[V.size()-2]>=V[V.size()-1] && x>=V[V.size()-1]) {
			ret+=min(V[V.size()-2],x);
			V.pop_back();
		}
		V.push_back(x);
	}
	sort(V.begin(),V.end());
	for(i=1;i<V.size()-1;i++) ret+=V[i-1];
	cout << ret << endl;
}

まとめ

終わってみるとあっさりだが、これ本番中には思いつかないなぁ。