超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC023D解いてみた

ABC023Dを解いてみました。
まずlogの計算で詰まってしまった(*_*)。最大で O(N log ( N) log (H + NS)) の計算量となるはずですが、するとN=10^5 S,H=10^9を代入してlog_2 10=0.3で計算すると O( 10^5 10^{1.5} 10^{4.5})=O(10^{11})で終わるわけねーだろ😡って思い込んでいたんですが、logの計算間違えてましたね😭。正しくは O( 10^5 \times 1.5 \times 4.5)=O(6 \times 10^5)ということで、logは要注意。
追記
なんかいろいろと勘違いしてました。log_2 10=3.3 O( 10^5 \times 16.5 \times 49.5)=O(10^8)ですね。対数は本当難しい。
下記のコードでは通りません

#include <algorithm>
#include <cstdio>
#define MAX_N  100000
 
using namespace std;
 
int N;
int H[MAX_N];
int S[MAX_N];
long long temp[MAX_N];
 
bool isOK(long long point) {
  for(int i=0;i<N;++i) {
    temp[i] = (point-H[i]) / S[i];
    //--from
    if (temp[i]<0) return false;
   //--to
  }
  sort(temp, temp+N);
 
  for(int i=0;i<N;++i) {
    if (temp[i]<i) {
      return false;
    }
  }
  return true;
}
 
long long solve(long long l, long long r) {
  if (l==r-1) {
    return r;
  }
  if(isOK((l+r)/2)) {
    return solve(l, (l+r)/2);
  } else {
    return solve((l+r)/2, r);
  }
}
 
int main() {
  scanf("%d", &N);
  for(int i=0;i<N;++i) {
    scanf("%d%d", &H[i], &S[i]);
  }
 
  printf("%lld\n", solve(1, (1000ll*1000ll*1000ll*1000ll*1000ll)));
 
 
  return 0;
}

なぜか通らない。詰まった原因は上記from~toのところ。ここで、point-H[i]<0になる時は、temp[i]も負になるというつもりで書いたが、実際はS[i]で割っているので場合によっては負の数でも0に潰れて、正しく比較ができなくなってしまう。
よって下記のようなコードを追加するべきだった。

    if (point-H[i] < 0) {
      temp[i] = -1;
    }