Codeforces ECR #164 : E. Chain Reaction

こちらはそこまで難しくないかも。
https://codeforces.com/contest/1954/problem/E

問題

N体のモンスターが並んでおり、i番目のモンスターの体力はA[i]である。
ここで攻撃力Kの魔法を使い、モンスターを全滅させることを考える。
1体モンスターを選んで魔法を放つと、モンスターと隣接している生きているモンスターに連鎖的にKのダメージを与えられる。
体力が0以下になったモンスターは死亡したとみなす。

モンスターを全滅させるのにかかる最小魔法回数を、K=1～max(A)のそれぞれに対し求めよ。

解法

魔法は、生きているモンスターのうち最も手前に並んだモンスターに使うとする。
すると、モンスターiに魔法を放つのは、ceil(A[i-1]/K)＜cel(A[i]/K)の時だけである。

A[i-1]＜A[i]に対し、ceil(A[i-1]/K)やcel(A[i]/K)の値が変化するKを総当たりすれば、KごとにA[i]に使う魔法の回数が求められる。
それらの累積和を取ればよい。

int N,A[101010];

ll D[101010];

int nexv(int d,int x) {
	if(x<=d) return 1<<20;
	int v=(x+d-1)/d-1;
	
	int nv=x/v;
	while((x+nv-1)/nv==(x+d-1)/d) nv++;
	return nv;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ma=0;
	FOR(i,N) {
		cin>>A[i+1];
		ma=max(ma,A[i+1]);
	}
	
	FOR(i,N) if(A[i]<A[i+1]) {
		x=A[i];
		y=A[i+1];
		int d=1;
		int pd=y-x;
		D[d]+=pd;
		while(d<=ma) {
			int nex=nexv(d,x);
			int ney=nexv(d,y);
			d=min(nex,ney);
			if(d>ma) break;
			D[d]-=pd;
			pd=(y+d-1)/d-(x+d-1)/d;
			D[d]+=pd;
			
		}
	}
	
	for(i=1;i<=ma;i++) {
		D[i]+=D[i-1];
		cout<<D[i]<<" ";
	}
	cout<<endl;
	
	
		
}

まとめ

なるほど…。