C++で指定した桁和を持つN以下の数をカウントする方法

数字からなる文字列 str と目標の合計値 total が入力として与えられます。この記事では、str で表される数 N 以下の整数のうち、各桁の数字の合計が total と一致するものの個数を求める方法を解説します。

具体例で理解しよう

例 1

入力: N="110"、sum=5

出力: 指定した桁和を持つ N 以下の数の個数: 7

説明: 110 以下で桁の合計が 5 になる数は次の通りです。

5, 14, 23, 32, 41, 50, 104

例 2

入力: N="1000"、sum=3

出力: 指定した桁和を持つ N 以下の数の個数: 10

説明: 1000 以下で桁の合計が 3 になる数は次の通りです。

3, 12, 21, 30, 102, 111, 120, 201, 210, 300

プログラムで使用するアプローチ

このアプローチでは動的計画法(DP)を用いて、途中結果を三次元配列 arr[18][2][162] にキャッシュします。ここで、18 は最大 18 桁の数に対応し、2 は状態フラグ用の値 0 と 1、162 は全 18 桁が 9 だった場合の最大桁和(18 × 9 = 162)に対応しています。

配列の要素 arr[i][j][k] は、「先頭から i 桁分を確定させたときの、桁和が k になる数の個数」を表します。j の値は、現時点で構築中の i 桁の数が N の先頭 i 桁と一致しているかどうかを示すフラグです(j=1 なら一致、j=0 ならすでに N より小さい)。たとえば N=123 で i=2 のとき、先頭 2 桁が 12 と一致していれば j=1、そうでなければ j=0 となります。

再帰の終端では、i が N の桁数に達し、かつ累積桁和 k が入力の total と一致すれば 1 を返し、そうでなければ 0 を返します。

次の桁(i+1 桁目)を決めるときは、フラグ j の値に応じて選べる数字の範囲が変わります。

• j=1 の場合: 先頭 i 桁が N と一致しているため、次の桁には「N の i+1 桁目以下の数字」しか選べません。これにより、構築中の数が N を超えるのを防ぎます。
• j=0 の場合: すでに構築中の数が N より小さいことが確定しているため、次の桁には 0〜9 のどの数字を選んでも N を超えることはありません。

すべての桁を処理し終えたら、集計した個数を最終結果として返します。

アルゴリズムの手順

• 数 N を表す文字列 str と、目標の桁和 total を受け取ります。
• 配列 arr[18][2][162] を用意し、memset を使ってすべて -1 で初期化します(-1 は「未計算」を意味します)。
• 関数 count_digits(int i, bool check, int temp, int total, string str, int size) が再帰的に arr[][][] を埋めながら、最終的に条件を満たす数の個数を返します。
• 現在の桁位置 i が N の桁数と一致し、かつ現在の累積桁和 temp が total と一致する場合は 1 を、そうでなければ 0 を返します。
• count = arr[i][check][temp] を参照し、値が -1 でなければ(計算済みであれば)その値を即座に返して重複計算を回避します。
• 一時変数 check_2(bool 型)と temp_2(int 型)を用意します。
• for ループで数字 '0'〜'9' を順に試します。check が 0(N と一致中)の場合は、現在の数字 ch が str[i] より大きければループを抜けます。
• check_2 = check || ch < str[i] を設定します(一度でも N より小さくなったら、以降ずっとその状態を維持します)。
• temp_2 = temp + (ch - '0') として新しい累積桁和を計算します。
• count += count_digits(i + 1, check_2, temp_2, total, str, size) で再帰呼び出しを行い、結果を加算します。
• すべての数字を試し終えたら count を返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, string str, int size) {
    if (i == size) {
        if (temp == total) {
            return 1;
        } else {
            return 0;
        }
    }
    int count = arr[i][check][temp];
    if (count != -1) {
        return count;
    }
    count = 0;
    bool check_2;
    int temp_2;
    for (char ch = '0'; ch <= '9'; ch++) {
        if (!check) {
            if (ch > str[i]) {
                break;
            }
        }
        check_2 = check || ch < str[i];
        temp_2 = temp + (ch - '0');
        count += count_digits(i + 1, check_2, temp_2, total, str, size);
    }
    return count;
}
int main() {
    string str = "1101";
    int size = str.size();
    int total = 5;
    memset(arr, -1, sizeof(arr));
    cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

Count of numbers smaller than or equal to N with given digit sum are: 26

計算量

• 時間計算量: O(桁数 × 2 × 最大桁和 × 10)。各状態について 0〜9 の数字を一度だけ試すため、非常に効率的です。
• 空間計算量: O(桁数 × 2 × 最大桁和)。メモ化テーブルのサイズに依存します。

このように、桁 DP(桁ごとの動的計画法)を活用することで、単純な全探索では膨大な時間がかかるような大きな N に対しても、高速に答えを求めることができます。