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=1018であれば、答えは1018-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; }
