ABC146C - Buy an Integerを二分探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 146 C - Buy an IntegerをCommon Lispで解いてみました。

まず問題文を見ます。
1以上10の9乗以下の整数のうち、$A \times N + B \times d(N) \le X$を満たす最大の数$N$を求める問題です。
問題文の時点で1から順番に試していく方法は使えないことがわかります。
二分探索であれば、$O(\log N)$で間に合うので二分探索を使う方向で考えます。

次に制約をみますが、特に方針に影響はなさそうです。

問題文の式から、整数が大きくなると値段も高くなることがわかります。
整数をひとつも買えないときは$0$を返すというところを少し読み替えて、商品に$0$を追加し、常に購入できるとします。
また、絶対に購入できない数として$10^9+1$を商品に追加します。
こうすることで、途中で条件を満たさなくなる単調性のある数列を用意できました。

あとは二分探索で答えを求めます。

(let* ((a (read))
       (b (read))
       (x (read)))

  (labels ((cost (n)
             ;; 代金を計算する
             (+ (* a n)
                (* b (length (format nil "~A" n)))))

           (bsearch (min max)
             ;; 購入できる最大の整数を二分探索する
             (if (= (1+ min) max)
                 min
                 (let ((mid (+ min (floor (- max min) 2))))
                   (if (<= (cost mid) x)
                       (bsearch mid max)
                       (bsearch min mid))))))

    (format t "~A~%" (bsearch 0 (1+ (expt 10 9))))))
  

AtCoder Beginner Contestを解いてみたリスト