FII Code 2020 Round #1 : D. Driveaway

久々のCSA。昨年FII Codeは出てないので。
https://csacademy.com/contest/fii-code-2020-round-1/task/driveaway/

問題

N要素の数列A[i]が与えられる。数列の各要素を取得するのにかかるコストをA[i]とする。
ここでK組の隣接要素を選ぶことを考える。(複数の組で同じ要素を複数回選ぶことはできない)。
選んだ要素の値の和がSの時、与えられる定数Kに対しmin(S,K)だけコストを浮かせることができる。

K=1～floow(N/2)に対し、全要素の取得コストの最小値を求めよ。

解法

Kを1ずつ増す際、アプローチは以下のいずれかである。

• まだ選ばれていない隣接２要素を新規に選ぶ。
• すでに連続する2m要素が選ばれていて、その両隣が選ばれていない場合、組み合わせて両隣を含む2(m+1)要素で(m+1)組を作る。

まず累積和を取り、連続する2m要素を2個ずつ組みにした場合に浮くコストの総和をもと止めておく。
そうすると、上記アプローチのうち後者のケースもO(1)でコストの低下分の差分を求められる。

あとは、上記２アプローチをsetやpriority_queueで管理し、コスト削減幅が最大のものをどん欲に選んでいく。

int N,X;
int A[202020];
ll S[2][202020];

ll pt(int cur,int ri) {
	ll ret= (S[ri%2][ri+1]-S[ri%2][cur])-(S[(ri+1)%2][ri]-S[(ri+1)%2][cur+1]);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	ll sum=0;
	FOR(i,N) {
		cin>>A[i];
		sum+=A[i];
	}
	FOR(i,N) {
		S[0][i+1]=S[0][i];
		S[1][i+1]=S[1][i];
		if(i) S[i%2][i+1]+=min(X,A[i]+A[i-1]);
	}
	
	set<pair<ll,int>> C;
	set<int> alive;
	
	FOR(i,N-1) C.insert({min(X,A[i]+A[i+1]),i});
	alive.insert(-1);
	alive.insert(N);
	FOR(i,N) alive.insert(i);
	FOR(i,N/2) {
		auto it=C.rbegin();
		sum-=it->first;
		x=it->second;
		C.erase(*it);
		
		auto cur=alive.lower_bound(x);
		auto ri=next(cur);
		auto ri2=next(ri);
		auto le=prev(cur);
		x=*le;
		y=*ri2;
		j=*cur;
		r=*ri;
		
		if(y<N) C.erase({pt(r,y),r});
		if(x>=0) C.erase({pt(x,j),x});
		alive.erase(j);
		alive.erase(r);
		if(x>=0&&y<N) C.insert({pt(x,y),x});
		cout<<sum<<endl;
	}
	
	
}

まとめ

Round1だしDiv2相当かと思ったけど、Div1.5ぐらいの難易度に思えた。