AtCoder ABC246で不正解になった問題を解いてみた

概要

AtCoder ABCに参加して私が不正解になった問題を再度解いてみる。
最適な解法はAtCoderサイトの解説をご確認いただきたいが、自分なりに解いていく過程を書いていきたいと思う。
今回はABC246。以下を自分なりに解いてみた。

• 不正解問題：D問題

ABC246 D問題：2-variable Function

問題文リンク
下記を満たす最小のXを求める問題。

X=a^3+a^2b+ab^2+b^3 (整数a\geqq 0,整数b\geqq 0)\\
0\leqq N\leqq X\leqq 10^{18}

解く過程での私の思考

1. 変数a,bは非負整数なので、a1<a2だとX(a1,b)<X(a2,b)が成り立つ。bも同様。
   また、X(a,b)=X(b,a)も成り立つ。
2. a,bの範囲として考えておく必要がある上限は高々Nの三乗根であろう。
3. 以下のように後は最小値を追い込んでいけばよいはず。
   1. Nの三乗根以上の最小の整数をb0として、X(0,b0)を候補値minXとする。
   2. bをデクリメントしていきmin(minX,X(a,b))でminXを更新していき、X(a,b)がN以下になるまで進める。
   3. aをインクリメントする。
   4. 2./3.を繰り返し、a=bになれば終了。

下図で赤はN以上の(a,b)組み合わせ、黄はN未満、灰色は結果探索しないことになる組み合わせを示す。

私が正解に辿り着けたコードは以下。

int main() {
  int64_t N;
  cin >> N;
 
  // X >= N
  // X = a^3 + a^2 * b + a*b^2 + b^3
  double root3N = pow((double)N,(double)1/(double)3) ;
  int64_t maxB = (int64_t)root3N + 1;
 
  int64_t A = 0 ;
  int64_t B = maxB ;
  int64_t minX = (A+B) * (A*A + B*B) ;
  int64_t currX ;
  bool b_decr = true;
  while ( A <= B ){
    if (b_decr) B--;
    else A++ ;
    currX = (A+B) * (A*A + B*B) ;
    if (currX<N){
      b_decr = false;
      continue;
    }
    b_decr = true;
    minX = min(minX, currX);
  }
  cout << minX << endl;
  return 0;
}