ABC023 D - 射撃王
2019/10/25
$ N個の風船を射撃で割る
風船$ iは競技開始時高度$ H_iにあり、1秒に$ S_iだけ増加する
競技開始から$ 0~$ N-1秒に1秒にに1個ずつ割ることができる
風船を割る瞬間の高度の最大値の最小値を求めてください
ポイント
高度の最大値の最小値には、実現可能性に関して単調性がある(解決め打ち二分探索ができる)
高度の最大値$ Xを実現できるなら、$ X+1も実現できる
高度の最大値$ Xを実現できないなら、$ X-1も実現できない
高度$ Xが実現できるかどうかの判定問題を解く
ある風船に対して$ t秒以内に射撃しないといけないという制限時間が計算できる
$ H_i + S_i \times t_i \leq Xより、
$ t_i \leq \frac{X-H_i}{S_i}となる
※$ X < H_iのとき、実現不可能(開始時に高度$ H_iが$ Xを上回っていたら、無理)
$ t秒以内の配列ができたら、それの前からの累積和を取ることで、$ t秒以内に処理すべき個数が計算される
$ 0秒から処理を開始できるので、$ t秒以内には最大で$ t + 1個の風船を処理できる。つまり、$ t秒以内でそれより多い風船の処理を求められたら不可能という話。
解説記事
自分なりの解説
ポイントで書いてしまったので書くことがなくなった・・・
想定解法は高度$ Xが実現されるかを判定するとき、$ t秒の配列の小さいものから貪欲に処理していく解法だった。自分の解法はsortがいらないので、計算量改善されている。
類題
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define all(a) (a).begin(),(a).end() using P = pair<int, int>;
typedef long long ll;
const ll INFLL = 1LL << 60;
ll N;
vector<ll> H,S;
bool check(ll X){
vector<ll> cnt(N,0);
rep(i,N){
//N-1秒以内のものだけ。それより後でもいいものはいつやってもいい
}
//累積和を取ることでt秒以内の数を数え上げられる
//1秒で一個しか処理できないので、それがt+1を越えるとき、false
vector<ll> cum(N,0);
for(int i = 0; i < N-1; ++i){
}
rep(t,N){
return false;
}
}
return true;
}
int main() {
cin>>N;
H.resize(N);S.resize(N);
rep(i,N){
}
ll ng = 0, ok = INFLL;
while(ok-ng>1){
ll mid = (ok + ng)/2;
if(check(mid)){
ok = mid;
}
else{
ng = mid;
}
}
cout<<ok<<endl;
}