C++で解く連続数字（シーケンシャルディジット）問題：アルゴリズムと実装例

問題の概要：連続数字（Sequential Digits）とは

ある整数が連続した桁（シーケンシャルディジット）を持つとは、その数値の各桁が、直前の桁よりも必ず1大きくなっている状態を指します。例えば 123 や 4567 のような数値が該当します。

この記事では、指定された範囲 [low, high] に含まれる連続数字をすべて見つけ、昇順に並べたリストとして返す方法を解説します。例として、low = 100、high = 300 が与えられた場合、条件を満たすのは 123 と 234 の2つだけであるため、出力は [123, 234] となります。

解法のアプローチ

連続数字は「先頭の桁」と「桁数」が決まれば一意に定まるため、この2つの組み合わせを全通り試して候補を生成するのが効果的です。具体的な手順は以下の通りです。

• 結果を格納するための配列 res を作成します。
• 外側のループで桁数 i を 1 から 9 まで変化させます。
• 内側のループで先頭の桁 j を 1 から始め、j + i − 1 ≤ 9 を満たす間繰り返します。
• 各組み合わせに対して、x := 0 と初期化し、k を 0 から i − 1 まで回しながら x := 10 × x + (j + k) と更新することで、連続数字を構築します。
• 構築した x が low ≤ x ≤ high を満たす場合、ans に追加します。
• すべての候補を確認し終えたら、ans を返します。

連続数字の候補は最大でも 9 + 8 + … + 1 = 45 個しか存在しないため、この手法は非常に高速に動作します。また、候補は小さい数から順に生成されるため、追加のソート処理も不要です。

C++での実装例

それでは、実際のコードを見ながら理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> sequentialDigits(int low, int high) {
      vector <int> ans;
      for(int i = 1; i <= 9; i++){
         for(int j = 1; j + i - 1 <= 9; j++){
            int x = 0;
            for(int k = 0; k < i; k++){
               x = (x*10) + (j + k);
            }
            if(low <= x && x <= high){
               ans.push_back(x);
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.sequentialDigits(500, 5000));
}

入力

500
5000

出力

[567, 678, 789, 1234, 2345, 3456, 4567]

この実行例では、500 以上 5000 以下の範囲に含まれる連続数字として、567、678、789、1234、2345、3456、4567 が正しく検出されています。このように、先頭の桁と桁数を組み合わせて数値を構築するシンプルなアプローチで、範囲内の連続数字を漏れなく効率的に列挙できます。