C++で長さnの回転対称数（ストロボグラマティック数）をすべて生成する方法

問題の概要

長さ n が与えられたとき、その長さをもつすべての回転対称数（ストロボグラマティック数）を求めることを考えます。

回転対称数とは、180度回転させても見た目が変わらない数のことです。回転しても有効な数字と対応する組み合わせは、次の5種類だけです。

• 0 ↔ 0
• 1 ↔ 1
• 8 ↔ 8
• 6 ↔ 9
• 9 ↔ 6

奇数桁の数では、中央に置けるのは回転しても自分自身である 0・1・8 の3種類に限られます。

たとえば入力が n = 2 の場合、出力は ["11", "69", "88", "96"] となります。「69」は180度回転しても「69」に見えるため、条件を満たしています。

解法のアプローチ：中央から外側へ構築する

この問題は、内側（中央）から順に、左右へ回転対応する数字のペアを付け加えていくことで効率的に解けます。手順は以下の通りです。

1. 結果を格納する配列 ret を用意します。
2. n が奇数の場合は ret に「0」「1」「8」を追加します（中央に置ける数字）。偶数の場合は空文字列を追加します。
3. n > 1 の間、n を 2 ずつ減らしながら次の処理を繰り返します。
   • 一時配列 temp を用意します。
   • ret の各文字列 s に対して、「1s1」「8s8」「6s9」「9s6」を temp に追加します。
   • さらに n > 3 の場合のみ「0s0」も追加します。現在の層が後から外側のペアで包まれる場合に限って先頭の 0 を許すことで、先頭が 0 になる無効な数の混入を防ぎます。
4. 各ループの最後で ret を temp で置き換えます。
5. すべての桁を埋め終えたら ret を返します。

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

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

void print_vector(vector<string> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}

class Solution {
public:
   vector<string> findStrobogrammatic(int n) {
      vector<string> ret;
      if (n & 1) {
         ret.push_back("0");
         ret.push_back("1");
         ret.push_back("8");
      } else {
         ret.push_back("");
      }
      for (; n > 1; n -= 2) {
         vector<string> temp;
         for (int i = 0; i < ret.size(); i++) {
            string s = ret[i];
            if (n > 3) {
               temp.push_back("0" + s + "0");
            }
            temp.push_back("1" + s + "1");
            temp.push_back("8" + s + "8");
            temp.push_back("6" + s + "9");
            temp.push_back("9" + s + "6");
         }
         ret = temp;
      }
      return ret;
   }
};

int main() {
   Solution ob;
   print_vector(ob.findStrobogrammatic(3));
}

入力と実行結果

入力

3

出力

[101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 986]

出力されたどの数も、180度回転すると元の数に戻ります。例えば「609」は回転すると「609」、「986」は「986」となり、正しく回転対称の性質を満たしていることが確認できます。

計算量の目安

2桁増えるごとに候補の数は最大5倍に増加するため、生成される数の総数はおよそ 5^(n/2) 個、全体の計算量は O(n × 5^(n/2)) 程度になります。メモリ使用量も同様のオーダーです。n が大きくなると組み合わせが爆発的に増えるため、扱える桁数には自ずと限界がある点に注意しましょう。