AtCoder ABC 146 C - Buy an Integer (茶色, 300 点)

二分探索の教育的問題ですね！

問題へのリンク

問題概要

正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき

• 

を満たす最大の正の整数 を求めよ。

制約

• 
• 

考えたこと

わけわからない式だし、二分探索に決まってるやろ！！！という雰囲気がある。より一般には、正の整数 に対して単調増加な式 があるとき、

• を満たす最大の正の整数

は、二分探索によって求めることができる。具体的な方法としては、まずはなんといっても

• 絶対に を満たす 　(0 とかで OK)
• 絶対に を満たす 　(1000000001 とかで OK)

を確保する。そして毎回のステップで以下を繰り返す。

---

• = ( + ) / 2 として
• であれば、 = とする
• であれば、 = とする

---

重要なのは、この手続きによって

• は常に を満たし続ける
• は常に を満たし続ける

という状態をキープしながら、 と の幅を半減し続けることができる。最終的には

• は を満たす最大の値
• は を満たす最小の値

という状態に落ち着く。

#include <iostream>
using namespace std;

// 桁数
long long d(long long a) {
    long long res = 0;
    while (a) {
        ++res;
        a /= 10;
    }
    return res;
}

int main() {
    long long A, B, X;
    cin >> A >> B >> X;
    long long left = 0, right = 1000000001;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        if (A * mid + B * d(mid) > X) right = mid;
        else left = mid;
    }
    cout << left << endl;
}

二分探索の実装をラムダ関数化する

二分探索のロジック自体は毎回決まった形でかけるので、ラムダ式を用いた抽象化と相性がいい！！！

それをやってみる

#include <iostream>
using namespace std;

int main() {
    long long A, B, X;
    cin >> A >> B >> X;

    // 二分探索用の関数
    auto keta = [&](long long N) {
        long long res = 0;
        while (N) ++res, N /= 10;
        return res;
    };
    auto f = [&](long long N) {
        return A * N + B * keta(N);
    };

    // 二分探索
    long long left = 0, right = 1000000001;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        if (f(mid) > X) right = mid;
        else left = mid;
    }
    cout << left << endl;
}