Codeforces ECR #143 : E. Explosions?

7問回の5問目で割と難しかった回。
https://codeforces.com/contest/1795/problem/E

問題

N体の敵が並んでおり、それぞれの体力H[i]が与えられる。
これらの敵を倒したいが、その際1体の敵の体力を1減らすのにMP1を消費する。
敵の体力を0にするとその敵を倒すことができる。

ここで、1回だけ爆発魔法を放つことができる。
敵を1体指定し、エネルギーXを指定する。
するとMPをX消費し、その敵の体力をX減らすことができる。
その際、両隣の敵に、min(隣の敵の体力,(X-1))だけ体力を減らすことができる。
この挙動は連鎖的に発生し、どんどんとなりの敵の体力を減らすことができる。

全部の敵を倒すのにかかる最小MP量を求めよ。

解法

爆発魔法は最初に使うのが良く、敵を1体指定し、Xにその体力を指定するのが良い。
そこで爆発魔法を使う敵を総当たりしよう。
その前処理として、左右それぞれ爆発魔法の伝搬によりどの程度敵の体力の総数を削ることができるか求めておくと良い。

int T,N;
ll H[303030];
ll L[303030];
ll R[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		vector<pair<int,int>> ev1,ev2;
		ll S=0;
		FOR(i,N) {
			cin>>H[i];
			S+=H[i];
			ev1.push_back({H[i]-i,i});
			ev2.push_back({H[i]+i,-i});
		}
		sort(ALL(ev1));
		sort(ALL(ev2));
		set<int> did={-1,N};
		FORR2(h,i,ev1) {
			x=*prev(did.lower_bound(i));
			if(x==-1) {
				if(H[i]<=i+1) {
					L[i]=H[i]*(H[i]+1)/2;
				}
				else {
					L[i]=H[i]*(i+1)-1LL*i*(i+1)/2;
				}
			}
			else {
				L[i]=L[x]+H[i]*(i-x)-1LL*(i-x-1)*(i-x)/2;
			}
			did.insert(i);
		}
		did={-1,N};
		FORR2(h,i,ev2) {
			i=-i;
			x=*did.lower_bound(i);
			if(x==N) {
				if(H[i]<=N-i) {
					R[i]=H[i]*(H[i]+1)/2;
				}
				else {
					R[i]=H[i]*(N-i)-1LL*(N-i)*(N-i-1)/2;
				}
			}
			else {
				R[i]=R[x]+H[i]*(x-i)-1LL*(x-i-1)*(x-i)/2;
			}
			did.insert(i);
		}
		ll mi=S;
		FOR(i,N) {
			ll co=min(mi,S-(L[i]+R[i]-2*H[i]));
			mi=min(mi,co);
		}
		cout<<mi<<endl;
	}
}

まとめ

方針はすぐ立つけど、若干実装に戸惑うな。