C++で指定された数字集合から作れるN以下の整数の個数を求める方法

問題概要

ソート済みの数字集合 D が与えられます。これは {'1', '2', '3', '4', '5', '6', '7', '8', '9'} の空でない部分集合であり、0 は含まれません。ここで、これらの数字を何度でも繰り返し使って数値を書くことを考えます。

例えば、D = {'2','3','7'} の場合、「23」「771」「2372327」のような数値を書くことができます。

このとき、この方法で書くことのできる N 以下の正の整数 の個数を求めるのが本問題です。

例として、入力が D = [2, 3, 4, 7]、N = 100 である場合を考えます。このとき出力は 20 になります。実際に書ける数は、2, 3, 4, 7, 22, 23, 24, 27, 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77 の 20 個であり、それ以外の数はすべて 100 より大きいためです。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

• N を文字列 n に変換します。
• n の桁数を sz、答えを格納する変数を ret とします。
• まず、N より桁数が少ない数をすべて数えます。i 桁の数は自由に組み合わせられるため、ret += (Dのサイズ)^i を i = 1 から sz-1 まで足し合わせます。
• 次に、N と同じ桁数の数を上の桁から順に調べます。
  i = 0 から sz-1 までの各桁について:
  • hasSameNum := false と初期化します。
  • D 内の各数字 x について:
    • x[0] < n[i] の場合：その桁に x を置いた残りの桁は自由に選べるため、ret += (Dのサイズ)^(sz - i - 1) を加算します。
    • x[0] == n[i] の場合：N と一致する数字が存在するので hasSameNum := true とします。
  • N と一致する数字がその桁になかった場合（hasSameNum が false）、それ以降は N 以下の数を作れないため、ここで ret を返します。
• 最後まで処理が完了した場合、N 自身も条件を満たすので ret + 1 を返します。

それでは、理解を深めるために実装を見てみましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int atMostNGivenDigitSet(vector<string> &D, int N) {
        string n = to_string(N);
        int sz = n.size();
        int ret = 0;
        // Nより短い桁数の数をすべて加算
        for (int i = 1; i < sz; i++) {
            ret += pow(D.size(), i);
        }
        // Nと同じ桁数の数を上の桁から判定
        for (int i = 0; i < sz; i++) {
            bool hasSameNum = false;
            for (string &x : D) {
                if (x[0] < n[i]) {
                    ret += pow(D.size(), sz - i - 1);
                } else if (x[0] == n[i]) {
                    hasSameNum = true;
                }
            }
            if (!hasSameNum)
            return ret;
        }
        return ret + 1;
    }
};
main(){
    Solution ob;
    vector<string> v = {"2","3","4","7"};
    cout << (ob.atMostNGivenDigitSet(v, 100));
}

入力

{"2","3","4","7"}, 100

出力

20

計算量について

このアルゴリズムの時間計算量は O(sz × |D|) です。sz は N の桁数、|D| は使用できる数字の種類数を表します。N を全件走査することなく桁ごとの組み合わせを数学的にカウントするため、非常に大きな N に対しても高速に動作する点が大きな特徴です。