AtCoder ABC #153 : F - Silver Fox vs Monster

途中しょうもないミスで２分近くロスしたのがもったいない。
https://atcoder.jp/contests/abc153/tasks/abc153_f

問題

1次元の座標上にN体の敵がおり、座標X[i]と体力H[i]が与えられる。
1回魔法を唱えると、場所を指定し、そこを中心にD以下の距離にいる敵の体力をA削ることができる。
最小で何回魔法を唱えれば敵の体力を削り切れるか。

解法

先に敵をX座標順にソートしておく。
残された敵のうち、座標が最も小さい敵を選択し、そこから距離2D以下の敵の体力を削るようにする。

区間に対し減算を行うので、BITを使ってもいいし累積和でも対応できる。

int N,D,A;
pair<ll,ll> P[202020];
ll DD[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D>>A;
	FOR(i,N) {
		cin>>x>>y;
		P[i]={x,(y+A-1)/A};
	}
	sort(P,P+N);
	P[N]={1LL<<60,0};
	
	ll sum=0;
	FOR(i,N) {
		if(i) DD[i]+=DD[i-1];
		P[i].second-=DD[i];
		if(P[i].second>0) {
			x=lower_bound(P,P+N,make_pair(P[i].first+2LL*D+1,-1LL<<60))-P;
			sum+=P[i].second;
			DD[i]+=P[i].second;
			DD[x]-=P[i].second;
		}
	}
	cout<<sum<<endl;
	
	
}

まとめ

難易度よりも、DP中心で解法が偏ってるのが気になったな。