C++で隣り合う桁の差が同じ数をすべて求めるアルゴリズム

問題概要

長さ N の非負整数のうち、「隣り合う 2 つの桁の絶対差がすべて K に等しい」という条件を満たす数をすべて求めることを考えます。ただし、答えに含まれる各数値は、数値 0 自体を除いて先頭に 0 を付けてはいけません。また、答えは任意の順序で返して構いません。

例として、N = 3、K = 7 の場合、出力は [181, 292, 707, 818, 929] となります。ここで 070 は先頭に 0 が付いているため、有効な数とはみなされない点に注意してください。

解法のアプローチ

この問題は、桁を 1 桁ずつ伸ばしながら候補を段階的に構築していく動的計画法(DP)的な手法で効率よく解くことができます。各ステップでは、既存の数の末尾の桁に対して「+K」または「−K」した値が 0〜9 の範囲内であれば、その数字を新しい末尾として追加した数を次のレベルの候補とします。同じ数の重複登録を防ぐため、visited という集合で訪問済みの数を管理するのがポイントです。

初期状態で dp[1] に 1〜9 のみを格納することで、先頭が 0 になる無効な数を自動的に排除できます。ただし N = 1 の場合は「0」自体も有効な答えになるため、特別に 0 を追加する必要があります。

アルゴリズムの手順

• サイズ n + 1 の配列 dp を作成し、dp[1] に 1 から 9 を格納します。
• i を 1 から N − 1 まで繰り返します。
  • visited という集合を定義します。
  • j を 0 から dp[i] のサイズまで繰り返します。
    • x := dp[i][j]
    • lastNum := x の末尾の桁
    • digit := lastNum + K
    • digit が 0 以上 9 以下であり、かつ x × 10 + digit が未訪問であれば、dp[i+1] に x × 10 + digit を追加し、visited にも記録します。
    • digit := lastNum − K
    • 同様に、digit が範囲内かつ未訪問であれば、dp[i+1] に追加します。
• N が 1 の場合は、dp[N] に 0 を追加します。
• dp[N] を返します。

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

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> numsSameConsecDiff(int N, int K) {
      vector <int> dp[N + 1];
      for(int i = 1; i <= 9; i++){
         dp[1].push_back(i);
      }
      for(int i = 1; i < N; i++){
         set <int> visited;
         for(int j = 0; j < dp[i].size(); j++){
            int x = dp[i][j];
            int lastNum = x % 10;
            int digit = lastNum + K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
            digit = lastNum - K;
            if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
               dp[i + 1].push_back(x * 10 + digit);
               visited.insert(x * 10 + digit);
            }
         }
      }
      if(N == 1){
         dp[N].push_back(0);
      }
      return dp[N];
   }
};
main(){
   Solution ob;
   print_vector(ob.numsSameConsecDiff(3,7));
}

入力

3
7

出力

[181,292,707,818,929]

まとめ

このアルゴリズムでは、各段階で各候補から高々 2 つの新しい候補(+K と −K)が派生するため、生成される候補の総数は最大で指数的に増加します。しかし、visited 集合による重複排除と、0〜9 の範囲チェックによって無効な候補を早期に切り捨てることで、条件を満たす数だけを効率的に列挙できます。先頭ゼロの扱いと N = 1 の特殊ケースへの対応さえ押さえておけば、実装は非常にシンプルで堅牢になります。