肩こりがひどい

肩こりがひどいエンジニアのお話

競プロや研究について

【C++】D - Base n (ABC192)

問題概要

0 ~ 9 からなる文字列 X と,整数 M が与えられる. X に含まれる最も大きい数字を  d とする.  d+1 以上の整数  n を選んで  X n 進法表記の数とみなして得られる値のうち,  M 以下であるようなものは何種類あるか?

f:id:katakori3:20210221232103j:plain
問題

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

ポイント

  •  n 進数から 10 進数への変換
  • 二分探索
  • オーバーフローへの対処
  • コーナーケースを考える

解説

  •  n 進数から 10 進数への変換

    そもそも  n 進数とは,「n の累乗を位取りの基本とする」ものです. こんな感じで10進数から n 進数へ変換することができます.

f:id:katakori3:20210221232519j:plain
10 進数から 3 進数への変換

  • 1018 という数字を見たら二分探索を使うことを考える.

     d+1 から  M 進数まで判定していくと,時間が足りません.ここで, x n 進数への変換を  f(n) とすると,単調増加であることが分かるので,二分探索が使用できることに気が付きます.

    二分探索に関する詳しい説明は書籍やこちら(二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita)などにお任せするとして,二分探索を簡単に以下の図で説明します.

    簡単に言うと,二分探索は全探索のようにすべてを探索するのではなく,探索する幅を狭めていく方法です.これにより  O(\log M) の計算量で探索することができます.

f:id:katakori3:20210221234101j:plainf:id:katakori3:20210221234058j:plain
二分探索

  • オーバーフローへの対処

    今回, n が大きくなっていくと, n 進数へ変換したときにオーバーフローが発生する可能性があります.つまり, M 以上であるかの判定を愚直に行うことができません. ここで,判定のために以下の式を使用します.ただし,この式が成立するのは  v が整数のときのみです.

     v >\mathrm{floor}{\dfrac{M}{x}} が成立するときは, v > \dfrac{M}{x} が成立する

    なぜこの式が成り立つのかの詳細な証明は省きますが,イメージ的には以下の図で示した通りです.これでオーバーフローを防ぐことができました.

f:id:katakori3:20210221231803j:plain
数直線上で考える

  • コーナーケース

    今回のコーナーケースは  X が一桁のときです.この時は 任意の  n 進数で  X になります.

    f:id:katakori3:20210221231759j:plain
    コーナーケース

  • 進数変換の実装の説明

     value = value * n + int(c - '0') は何をしているのかを図解しました.

f:id:katakori3:20210222163059j:plain
進数変換の実装

サンプルコード

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
 
int main(){
    string x; cin >> x;
    ll m; cin >> m;

    // x が 1 桁だと,任意の n 進数で x のみ(1種類しかない)
    if (x.size() == 1) {
        if (stoi(x) <= m) cout << 1;
        else cout << 0;
        return 0;
    }

    int d = 0;
    for (char c : x) d = max(d, int(c-'0'));
    // 下限を d にしたのは,最終的に知りたい値が ac - (d+1) - 1 なので
    // 下限を ac, 上限を wa とおくと良いらしい
    ll ac = d, wa = m + 1;

    // 二分探索は上限と下限(閾値)が隣り合うまで行われる
    while(wa - ac > 1){
        ll wj = (ac + wa) / 2; // (waithing judge: wj 進数)で表した時に m 以下かどうか
        ll value = 0;
        for (char c : x){
            // オーバーフローを避けるためにこちら
            if (value > m / wj) value = m + 1; 
            // 進数変換
            else value = value * wj + (c - '0');
        } 
        if (value <= m) ac = wj;
        else wa = wj;
    }
    cout << ac - d;
    return 0;

}

参考

進数法の解説にはこちらの記事を参考にさせていただきました.

examist.jp

実装に関しては公式解説のものです. (勉強のために写経させていただきました.)

www.youtube.com