三分探索の前に微分を検討せよ

1100

  • ceil関数をひとまず無視してf(x)を微分して0とおき、その周辺のxのみ線形探索すればいい
// 微分による正当解法
void solve2(){
  ll n,d;
  cin>>n>>d;
  
  // 何日かかるか
  auto f = [&](ll x){
    ll days = x + ceil_div(d,x+1);
    return days;
  };

  ll sq = sqrt(d);
  ll left = sq-100;
  ll right= sq+100;
  if(left<0)left=0;

  FOR(i,left,right){
    if(f(i)<=n){
      p_yes();return;
    }
  }
  p_no();
}