ABC146 C - Buy an Integerを理解し忘れないようにする

https://atcoder.jp/contests/abc146/tasks/abc146_c

問題概要

高橋くんの所持金が$X$円のとき、高橋くんの買うことのできる最も大きい整数を求める。ただし、買うことのできる整数が 1 つもない場合は 0 を出力する。
整数Nを購入するには、$A \times N + B \times |N|$が必要

方針

整数$1$~$10^9$を2分探索して、$X$円が$A \times N + B \times |N|$円を超えるか超えないかの境界値を求めて、超えない方を出力

実装案1 lower_boundを使って実装(❌)

https://cpprefjp.github.io/reference/algorithm/lower_bound.html

1~10^9をvectorに入れて管理すると値追加の際にTLEになるので使えない。

実装案2 めぐる式2分探索を使って実装(⭕️)

https://takatoku-room.com/二分探索とめぐる式二分探索/

• 回答コード

https://atcoder.jp/contests/abc146/submissions/58135792

省略

int main()
{
  ll a,b,x;
  cin >> a >> b >> x;  
  ll left = 0,right = MI;
  auto isOK = [&](ll n) -> bool {
    ll d = to_string(n).size();
    ll calc = a * n + b * d;
    return calc <= x;
  };

  while (right - left > 1)
  {
    ll mid = (left + right)/2;
    if (isOK(mid)) left = mid;
    else right = mid;
  }
  cout << left << endl;
  return 0;
}