ABC153F - Silver Fox vs Monster (600)

F - Silver Fox vs Monster

概要

N体の敵が数直線上に並んでいる。i体目の敵の座標はX[i], HPはH[i]である。
次のような攻撃を好きなだけ行うことで敵を全滅させることを考える。最小の攻撃回数を求めよ。

• 数直線上の好きな点yを選ぶ
• y - Dからy + Dまでの範囲にいる敵にAのダメージを与える

制約

1 ≦ N ≦ 2 * 10^5
0 ≦ D ≦ 10^9
0 ≦ A ≦ 10^9
0 ≦ X[i] ≦ 10^9
1 ≦ H[i] ≦ 10^9

方針

数直線上の敵を左から倒してゆくことを考える。最も左の敵を倒すためには、少なくとも左の敵のHP分の爆弾を落とす必要がある。どこに落とすかだが、左の敵の右方でかつその敵に届くぎりぎりに落とすとよい。その後、残った敵に対して、同様に最も左の敵に当たるぎりぎりの右方に左の敵のHP分の爆弾を落とすことを繰り返してゆくと敵を全滅できる。

敵に与えるダメージを累積的に管理してゆく必要がある。この高速化はimos法が使える。

感想

コンテスト中は遅延セグ木と戯れてました。imosでできましたね。。

解答

Submission #9791232 - AtCoder Beginner Contest 153

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, ll> pil;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll n, d, a;
	cin >> n >> d >> a;
 
	vector<pil> v(n);
	rep(i, n) cin >> v[i].first >> v[i].second;	
	sort(v.begin(), v.end());
 
	vector<int> x(n);
	rep(i, n) x[i] = v[i].first;
	sort(x.begin(), x.end());
 
	vector<ll> dmg(n+1, 0);
	ll ans = 0;
	for(int i = 0; i < n; i++){
 
		ll h = v[i].second;
 
		if(h > dmg[i]){
 
			ll bom = (h - dmg[i] + a - 1) / a * a;
			ans += (h - dmg[i] + a - 1) / a;
 
			auto itr = upper_bound(x.begin(), x.end(), x[i] + 2 * d);
			int r = distance(x.begin(), itr);
			dmg[i] += bom;
			dmg[r] -= bom;
		}
 
		dmg[i+1] += dmg[i];
	}
 
	cout << ans << endl;
}