C++でnより小さい最も近い「タイディ数」を求めるアルゴリズム

「タイディ数（tidy number）」とは、すべての桁が非減少順（左から右へ向かって、等しいか大きくなっていく順序）に並んでいる数のことです。この記事では、ある数 n が与えられたとき、n 未満の数の中で最も近いタイディ数を求める方法を、C++のコード例とともに解説します。

例えば n = 45000 の場合を考えてみましょう。45000 は「4 → 5」と増加した後、「5 → 0」と減少しているため、タイディ数ではありません。45000 未満で最も近いタイディ数は 44999 となります。

アルゴリズムの考え方

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

1. 数を文字列として受け取り、右端（末尾）の桁から順に左へ走査します。
2. ある桁がその右隣の桁より大きい場合（タイディ性が崩れている箇所）、その桁を 1 減らし、それより右側のすべての桁を 9 に置き換えます。
3. この処理を左端の桁に達するまで繰り返します。

減らした桁より右側をすべて 9 にすることで、その桁の制約を満たしつつ、可能な限り大きな値（＝n に最も近い値）を維持できるのがポイントです。

C++での実装例

#include<iostream>
using namespace std;
string tidyNum(string number) {
    for (int i = number.length()-2; i >= 0; i--) {
        if (number[i] > number[i+1]) {
            number[i]--;
            for (int j=i+1; j<number.length(); j++)
                number[j] = '9';
        }
    }
    return number;
}
int main() {
    string str = "45000";
    string num = tidyNum(str);
    cout << "The tidy number is: " << num;
}

実行結果

The tidy number is: 44999

コードの解説

関数 tidyNum では、末尾から2番目の桁（インデックス length()-2）から走査を開始します。number[i] > number[i+1] が成立した場合、その桁を -- で 1 減らし、内側のループでインデックス i+1 以降のすべての桁を '9' に書き換えます。これにより、45000 → 44999 のように、n 未満で最大のタイディ数が得られます。

注意点

桁を 1 減らした結果、先頭の桁が '0' になるケースには注意が必要です。例えば n = 100 の場合、このアルゴリズムは文字列 "099" を返すため、実際の答えは 99 となります。実用上は、先頭の 0 を取り除く後処理を追加しておくと安全です。

まとめ

桁の走査は末尾から行い、タイディ性が崩れた箇所で「1 減らして以降を 9 で埋める」というシンプルな戦略により、計算量 O(桁数) で n 未満の最も近いタイディ数を求めることができます。