ABC023 D - 射撃王

D - 射撃王

概要

風船がN個あり、風船iは現在H[i]の高度にあり、1秒間に高度がS[i]上昇する。
現在の状態からスタートして0秒後、1秒後、…と1秒おきに1つずつ風船を撃ち、風船を割ってゆく。
各風船が割られたときの高度をその風船からのペナルティーとし、各風船のペナルティーの最大値を最小化したい。ペナルティーの最小値を求めよ。

制約

1 ≦ N ≦ 10^5
1 ≦ H[i], S[i] ≦ 10^9

方針

なんとなくS[i]が大きい順に撃ちたいが、サンプル1からその順にはなっていない。

視点を変えて、あるペナルティーx以内に抑えることができるかを考える。
これができると、2分探索によってxを探してゆくことができそう。そして実際に可能で、説明は下記の通り。

ペナルティーx以内に抑えようとしたとき、各風船は(x - H[i]) / S[i] 以内に撃てばよい。
各風船を(x - H[i]) / S[i] が小さい順に撃ってゆき、i番目(0-index)に撃つ風船がi秒より小さい時点で撃たなければならないときに、ペナルティーx以内には抑えられないことになる。

感想

(x - H[i]) < 0 のときにその時点でreturn falseする、というのがかなり重要。
(x - H[i]) < 0 であれば、時点0で高度H[i]がxより高いのでダメ。なのではじかなければいけないが、v[i] < i のところで勝手にはじかれそうな気がしてロジックを追加しなかった。しかしこれだとWAになってしまう。
実は|(x - H[i]) | < S[i] のときは(x - H[i]) / S[i] = 0になってしまうのではじかれないケースがあり、それでWAになった模様。

「各風船を(x - H[i]) / S[i] が小さい順に撃ってゆく」という貪欲が思いつかなかった時の解答です。
Submission #4735718 - AtCoder Beginner Contest 023

eraseがO(N)らしいのでTLEします。(WAは(x - H[i]) < 0のロジックがないため)

解答

Submission #4746064 - AtCoder Beginner Contest 023

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll N;
vector<ll> H;
vector<ll> S;
 
ll n = 1LL << 60;
bool cond(ll x){
	vector<ll> v(N, 0);
 
	rep(i, N){
		if(x - H[i] < 0) return false;
		v[i] = (x - H[i]) / S[i];
	}
 
	sort(v.begin(), v.end());
 
	rep(i, N){
		if(v[i] < i) return false;
	}
	return true;
}
 
// condを満たす最小のxを求める(lower_bound)
// 全てのxが条件を満たさない場合はnを返す(nはとりえない値)
ll lower_bound_cond(){
	ll lb = 0, ub = n;
 
	while(ub - lb > 1){
		ll mid = (lb + ub) / 2;
 
		if(cond(mid)) ub = mid;   // Answer is in (lb, mid]
		else lb = mid;            // Answer is in (mid, ub]
	}
 
	// now lb + 1 = ub
	return ub;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N;
	rep(i, N){
		ll h, s;
		cin >> h >> s;
		H.push_back(h);
		S.push_back(s);
	}
 
	cout << lower_bound_cond() << endl;
}