CSAcademy Round #46 : E. Ultimate Orbs

実装は少し面倒だけど、考えは簡単。
https://csacademy.com/contest/round-46/task/ultimateorbs/

問題

N個のオーブが一列に並んでおり、それぞれの重さはW[i]である。
オーブは、(自身の重さ+D)以下の隣接するオーブを吸収することができる。
吸収するとそのオーブは消え、その分の重さが自身の重さに追加される。

最適な順でオーブを吸収させた場合、最後に各オーブ1つだけを残すことができるか判定せよ。

解法

吸収先が軽い方が吸収しやすいので、最終的に残すオーブ以外同士で吸収しあうことは無駄である。
Dは非負なので、もともとW[i]がW中で最大のオーブは、他のオーブをすべて吸収できるため、明らかに条件を満たす。

そうでない場合どうするか。
オーブの列中で、自身の手前および奥にある最寄りの自身より重いオーブを考える。
オーブiに対し、それぞれをL[i],R[i]とする。
[L[i]+1, R[i]-1]の範囲のオーブはすべて吸収できるので、sum(W[(L[i]+1)...(R[i]-1)])+DがW[L[i]]やW[R[i]]以上ならL[i],R[i]を吸収できる。
さて、ここでL[i]またはR[i]がそれ自身を最後まで残すことができ、かつそれらを吸収できるならオーブiも最後まで残すことができる。

よって、各オーブに対しL[i]、R[i]を求めたうえで、オーブを重い順に条件を満たすか判定していけばよい。

int N,D;
int G[1010101];
ll S[1010101];
int L[1010101];
int R[1010101];

int ok[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	vector<pair<int,int>> cand;
	
	scanf("%d%d",&N,&D);
	FOR(i,N) {
		scanf("%d",&G[i]);
		S[i+1]=S[i]+G[i];
		cand.push_back({G[i],i});
	}
	
	vector<pair<int,int>> V;
	V.push_back({1<<30,-1});
	FOR(i,N) {
		while(V.back().first<=G[i]) V.pop_back();
		L[i]=V.back().second;
		V.push_back({G[i],i});
	}
	V.clear();
	V.push_back({1<<30,N});
	for(i=N-1;i>=0;i--) {
		while(V.back().first<=G[i]) V.pop_back();
		R[i]=V.back().second;
		V.push_back({G[i],i});
	}
	
	sort(ALL(cand));
	reverse(ALL(cand));
	FORR(c,cand) {
		x=c.second;
		if(L[x]==-1 && R[x]==N) {
			ok[x]=1;
		}
		else {
			if(L[x]>=0 && S[R[x]]-S[L[x]+1]+D>=G[L[x]]) ok[x]|=ok[L[x]];
			if(R[x]<N && S[R[x]]-S[L[x]+1]+D>=G[R[x]]) ok[x]|=ok[R[x]];
		}
	}
	FOR(i,N) if(ok[i]) _P("%d ",i+1);
	_P("\n");
	
	
}

まとめ

「条件を達成できるオーブをどうにか吸収できれば、自身も条件を達成できる」ということに気付けたら勝ち。