C++で指定範囲内のすべての「良い数」を出力する方法

この問題では、3つの整数 L・R・d が与えられます。目的は、L から R までの範囲内に存在する「良い数」のうち、いずれの桁にも d が含まれていない数をすべて出力することです。

良い数（Good Number）とは？

良い数とは、すべての桁において、その桁の数字が「自分より右側（下位）の桁の数字の合計」より大きくなっている数のことです。
例えば 732 は良い数です。7 > 3＋2 であり、3 > 2 という条件がどちらも満たされているからです。

問題例

入力：L = 400 , R = 500 , d = 3
出力：410, 420, 421

説明：400〜500 の範囲にある良い数は 410、420、421、430 です。しかし今回は 3 を含む数を出力できないため、430 は除外されます。

解き方のアプローチ

この問題はシンプルな全探索で解くことができます。指定された範囲内（L〜R）のすべての数値を1つずつ確認し、次の2つの条件を満たす場合のみ出力します。

• その数が良い数であること
• その数のどの桁にも d が含まれていないこと

良い数の判定方法

数値を最下位桁から上位桁へ向かって走査し、それまでに読み取った桁の合計値を保持します。走査中のある時点で「これまでの合計値」が「次に見る桁の数字」以上になった場合は、その数は良い数ではないため false を返します。最後まで条件を満たせば true を返します。

C++による実装例

#include<bits/stdc++.h>
using namespace std;

// n が良い数であり、かつ桁に d を含まないかを判定する
bool isValidNumber(int n, int d){
    int digit = n % 10;   // 最下位桁を取得
    int sum = digit;      // 右側の桁の合計
    if (digit == d)
        return false;
    n /= 10;
    while (n){
        digit = n % 10;
        // d を含む、または合計値以下の桁があれば良い数ではない
        if (digit == d || digit <= sum)
            return false;
        else{
            sum += digit;
            n /= 10;
        }
    }
    return true;
}

// 範囲 L〜R 内の良い数をすべて出力する
void printGoodNumbersLtoR(int L, int R, int d){
    for (int i = L; i <= R; i++){
        if (isValidNumber(i, d))
            cout << i << " ";
    }
}

int main(){
    int L = 400, R = 600, d = 3;
    cout << "All good numbers from " << L << " to " << R << " that do not contain " << d << " are :\n";
    printGoodNumbersLtoR(L, R, d);
    return 0;
}

出力結果

400 から 600 までの、3 を含まないすべての良い数：
410 420 421 510 520 521 540

計算量の目安

• 時間計算量：O((R − L + 1) × D)　※D は数値の桁数（最大でも log₁₀R 桁程度）
• 空間計算量：O(1)　※追加のメモリはほとんど不要です

まとめ

範囲内の各数値に対して「右から左への桁走査」と「禁止桁 d のチェック」を行うだけで、条件を満たすすべての良い数を効率よく列挙できます。全探索ベースのシンプルな手法ですが、範囲が極端に大きくなければ十分実用的な解法です。