ABC023D -射撃王（精選21）

問題

D - 射撃王

非常に難しくて詰まりました。

この手の特殊な関数を立てて二分探索する問題をたまに見ますが，二分探索の応用範囲の広さを感じます。

解説AC

解説見てもなかなか理解できませんでしたが，他の人の提出コードを参照しながら概ね理解できました。

ある時間よりも前に撃つ必要のある的の数をcount[時間]の配列においていますが，時間の上限は，的の数がn個なのでn-1となります。

count[min(N-1, (x - H[i]) / S[i])]++;

このようにして入力し，累積和をとって，判定する流れはなるほどでした。

何回かWAを重ねたのは，最後の出力のところです。
midを出力するとエラーになるケースがあり正しくはrightを出力します。
rightが条件を充たす下限になっている（midは条件を充たさない場合もある）ことに留意します。

提出コード

#include <bits/stdc++.h>
using namespace std;

long long N;
vector<long long>S,H;

int f(long long x){
  vector<int> count(N);
  for(int i=0;i<N;i++){
    if(x<H[i]){
      return 0;
    }else {
            count[min(N-1, (x - H[i]) / S[i])]++;
    }
  }
  for(int j=0;j<N-1;j++){
      count[j+1]+=count[j];
  }
  for(int j=0;j<N;j++){
    if(count[j]>j+1){
      return 0;
    }
  }
  return 1;
}

int main(){
  cin >>N;
  S.resize(N);
  H.resize(N);
  for(int i=0;i<N;i++){
    cin>>H[i]>>S[i];
  }
  long long left=-1;
  long long right=1e18;
  long long mid;
  while(right-left>1){
    mid=(left+right)/2;
    if(f(mid)){
      right=mid;
    }
    else{
      left=mid;
    }
  }
  cout<<setprecision(18)<<right<<endl;
  return 0;
}