けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

問題概要

正の整数  A, B, X が与えられる。正の整数  N に対して  d(N) N の桁数とする。このとき

  •  A \times N + B \times d(N) \le X

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

制約

  •  1 \le A, B \le 10^{9}
  •  1 \le N \le 10^{18}

考えたこと

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

  •  f(N) \le X を満たす最大の正の整数  N

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

  • 絶対に  f({\rm left}) \le X を満たす  {\rm left} (0 とかで OK)
  • 絶対に  f({\rm right}) \gt X を満たす  {\rm right} (1000000001 とかで OK)

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


  •  {\rm mid} = ( {\rm left} +  {\rm right}) / 2 として
  •  f({\rm mid}) \gt X であれば、 {\rm right} =  {\rm mid} とする
  •  f({\rm mid}) \le X であれば、 {\rm left} =  {\rm mid} とする

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

  •  {\rm left} は常に  f({\rm left}) \le X を満たし続ける
  •  {\rm right} は常に  f({\rm right}) \gt X を満たし続ける

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

  •  {\rm left} f({\rm left}) \le X を満たす最大の値
  •  {\rm right} f({\rm left}) \gt X を満たす最小の値

という状態に落ち着く。

f:id:drken1215:20200105151228p:plain

#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;
}