1426C - Increase and Copy ～三分探索の嘘解法でAC～

  • Quiz
  • AC
  • 解説
    • +1する操作を先にするが、何回必要かを三分探索した
    • +1の操作回数をx軸、N以上とするために必要な合計回数をy軸とすると下に凸の関数になるから
    • しかし、3分割した点a, bの値f(a)==f(b)の場合どうしたらよいのだろう？
    • left, rightどちらも切り捨てることができない。仕方ないのでそこでbreakし、left～rightで全探索したがテストケースによってはTLEするだろう
    • そういえばこの関数fは整数値にしか定義されず、連続関数ではない？よって三分探索は間違い？多分そういうことだろう
    • 整数の三分探索は危険ということを学んだ

f:id:peroon:20201009184814p:plain

ll N;

// n回ポケットを叩く(+1)
// 条件を満たすまで合計で何回必要か？
ll f(ll n){
  // n回操作１をする
  ll v = n+1;
  return (N-v+v-1)/v + n;
}

// for codeforces
void solve(){
  cin>>N;
  if(N==1){
    p(0); return;
  }
  else if(N==2){
    p(1); return;
  }
  
  ll left=0;
  ll right=1e9;
  while(right-left>2){
    ll a = 2*left + 1*right; a/=3;
    ll b = 1*left + 2*right; b/=3;
    if(f(a)<f(b)){
      right = b;
    }else if(f(a)>f(b)){
      left = a;
    }else{
      break;
    }
  }
  ll mi=inf;
  FOR(i,left,right+1){
    chmin(mi, f(i));
  }
  p(mi);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; cin>>N;
    while(N--)solve();
    
    return 0;
}

追記：2020/10/16

全く同じミスをした