garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

Atcoder Beginner Contest 192_D "Base n"

Atcoder 水色 二分探索

水色の問題.本番だとしんどそう.

atcoder.jp

問題の説明

数字の0から9までで成される文字列Xと整数Mが与えられる.Xに含まれる最大の数字がdであるとき,ある整数n(n\le d)進法の数としてXをみる.このようにしてn進表記された数としてみたXの値のうちM以下となるものは何種類あるか.

制約

  • Xの長さは1以上60以下.
  • 1 \le M \lt 10^{18}

考えた事

まずXをp進表記された数として見た時の値を考えよう.この値をf(p)とし,Xのsizeをlとおくと,

f(p)=X\lbrack 0 \rbrack p^{l-1}+X\lbrack 1 \rbrack p^{l-2}...X\lbrack l-1 \rbrack p^{0}

となる.これがM以下であればいいのだから,

f(p) \le M...(1)

を満たすようなpについて考察すると答えに辿り着けそうだ.ここでf(p)の性質に注目すると,これはl-1次函数であるからpが非負整数である時に狭義単調増加する性質をもつ.つまりpがある一定値までの時は(1)を満たすが,もしそれを超えたらその先では絶対に(1)を満たさないのだ.

このようなある一定ラインを超える(or 下回る)時に状態がパッキリ割れるような問題で,その一定ラインの検出を高速で行えるアルゴリズムがあった.そう,二分探索である.二分探索を行えば(1)を満たすギリギリのpを見つけ出せる.そうすれば解としてp-dを出力すれば答えになりそうである.なぜなら今回の問題はf(p)がpに対して「狭義」単調増加性を有しており,pの変化に合わせてf(p),つまりXの値も変わるからである.

ここまでが考察の大筋である.さて,この考察は正しいだろうか.

恐らく試験の答案でこの議論をした場合,それなりに点を引かれてしまうだろう.どこがいけないだろうか.

答えは狭義単調増加性の部分だ.実は成り立たない場合がある.それはいつか.

l=1の時だ.このときf(p)は定数函数となり,pによらず取る値の種類は高々1つとなる.これを別立てて計算しておく必要がある. 具体的には,

if (X.size() == 1) {
        if (M - stoll(X) >= 0) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }

とするといい.Mとの大小関係で答えが分岐する.

やや長くなってしまったがここまでで問題の考察はできた.つづいて実装である.これがやや難しい.

f(p)はl=60近い値であるとき非常に大きな値となり,C++ではoverflowしてしまいそのままでは大小比較ができない.どうすればいいか.

こういった場合は「Mをpでl-1回割った値が0以上ならp^{l-1} \le Mでoverflowしていないから安心してM-X\lbrack 0 \rbrack p^{l-1}を行う.」といった所作を繰り返すといい.

つまりいきなり掛けるのではなく,まず割って確認すればいいのだ.このテクニックはちょくちょく出てくる.自分のコードでは念のため,X\lbrack 0 \rbrack p^{l-1}で割っているため,X\lbrack i \rbrack==0であるときの例外処理を書いていてやや煩雑となっている.

これに気を払えばあとはよくある二分探索の実装に載せるといい.とはいえ二分探索は往々にしてバグりやすい.これを防ぐために,

   ll ok = 0;
   ll ng = 4 * INF;
   while (abs(ok - ng) > 1) {
    ~~~
   }

のように絶対大丈夫なラインと絶対ダメなラインとで半開区間を考えるといい.この場合は\lbrack ok, ng)のような半開区間を想定している.

また,while内を絶対値で取っている理由もある.もし,(ng, ok \rbrackのような半開区間を考えたい時は,

   ll ok = 1000;
   ll ng = -1;
   while (abs(ok - ng) > 1) {
    ~~~
   }

のように数値を変えるだけで式を変えずに操作を行える.これがいわゆる「めぐる式二分探索」1である. なにはともあれ,ここまでくれば後はコードを載せればわかるだろう.ここまでお読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
int main() {
    string X;
    cin >> X;
    ll M;
    cin >> M;
    if (X.size() == 1) {
        if (M - stoll(X) >= 0) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    } else {
        ll num = 0;
        rep(i, X.size()) { CHMAX(num, (ll)(X[i] - '0')); }
        ll ok = 0;
        ll ng = 4 * INF;
        while (abs(ok - ng) > 1) {
            ll mid = ok + (ng - ok) / 2;
            ll res1 = M;
            bool flag = true;
            rep(i, X.size()) {
                ll res2 = res1;
                if ((X[i] - '0') == 0) {
                    continue;
                }
                rep(j, X.size() - i - 1) { res2 /= mid; }
                res2 /= (X[i] - '0');
                if (res2) {
                    ll res3 = (X[i] - '0');
                    rep(j, X.size() - i - 1) { res3 *= mid; }
                    res1 -= res3;
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        cout << max(ok - num, (ll)0) << endl;
    }
}

  1. https://twitter.com/meguru_comp/status/697008509376835584↩