Base n [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) D]

https://atcoder.jp/contests/abc192/tasks/abc192_d

前提知識

• 二分探索

解説

https://atcoder.jp/contests/abc192/submissions/20345441

誤読してしまったが、それもまた競プロなので問題を責めるべきではない。

場合分け

例えば、X=1, M=10の場合はどのようなnを選択しても、得られる値は1であり、M以下である。
だが、この場合でも「みなして得られる値」の個数としては1個である。
このように、|X|=1の場合は、どのようなnであっても同じ値となる。
よって、|X|=1だけ場合分けを行う。
X≦Mかを判定して、そうならば1だし、そうでないなら0が答え。
1＜|x|であれば、nが変われば値は必ず変わるので、数が重複してしまう問題については無視していい。

考え始め

まず、X=10, M=10¹⁸であれば、答えは10¹⁸-1になるので、答えを全探索していく方法は微妙。
といって、DPできそうな感じもないので、二分探索かなという感じ。

二分探索

nについて、M以下となるかは単調性を持つ。
具体的にはある値を境にそれ以下であればM以下だし、それより大きいならばMより大きい。
よって、あるnについてM以下であるかの判定関数checkを作れば、それを使って二分探索ができる。

check関数

問題文に言われた通りに行うと、Xをn進数表記に変換していく作業をして、M以下であるかを判定すればいい。
これをそのまま行うとlong longを使ってもオーバーフローしてしまうので、Mをn進数表記に変換して、比較をする実装を行っている。
n進数変換を説明するのは面倒なので、ググってみてほしい。
まあ、問題文で唐突に「n進数表記」と出て理解してるなら、ここは大丈夫か。
あとは、大小比較はサイズを比較して、先頭から順に大小比較していく。

string X; ll M;
//---------------------------------------------------------------------------------------------------
bool check(ll n) {
    vector<ll> Y;
    ll m = M;
    while (0 < m) {
        Y.push_back(m % n);
        m /= n;
    }
    reverse(all(Y));

    if (X.size() < Y.size()) return true;
    else if (X.size() > Y.size()) return false;
    
    // the same size.
    int len = X.size();
    rep(i, 0, len) {
        ll x = X[i] - '0';
        ll y = Y[i];

        if (x == y) continue;
        else if (x < y) return true;
        else return false;
    }

    // X == Y
    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> M;

    if (X.length() == 1) {
        ll x = stoll(X);
        cout << (x <= M ? "1" : "0") << endl;
        return;
    }

    int ma = -1;
    fore(c, X) chmax(ma, c - '0');

    ll ok = ma, ng = infl;
    while (ok + 1 < ng) {
        ll md = (ok + ng) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }

    ll ans = ok - ma;
    cout << ans << endl;
}