C++で挑むストロボグラム数問題③：範囲内の出現数を数える方法

ストロボグラム数とは？

ストロボグラム数（strobogrammatic number）とは、数字を180度回転させても同じように見える数のことです。回転しても元の形を保てるのは「0」「1」「8」の3種類だけで、さらに「6」と「9」は互いに入れ替わるペアとして機能します。これらの数字だけを組み合わせることで、回転対称となる数を作れます。

例えば、low = "50"、high = "100" という入力が与えられた場合を考えてみましょう。この範囲に含まれるストロボグラム数は 69・88・96 の3つであるため、出力は 3 になります。

解法のアプローチ

この問題は「指定した桁数のストロボグラム数をすべて生成する」→「low 以上 high 以下に収まるものだけを数える」という2段階で解きます。具体的な手順は以下の通りです。

ステップ1：findStrobogrammatic() 関数を定義する

• 桁数 n を受け取り、その桁数のストロボグラム数をすべて返す関数 findStrobogrammatic() を定義します。
• 結果を格納する配列 ret を用意します。
• n が奇数の場合（n & 1 が非ゼロの場合）、中央に置ける数字は「0」「1」「8」のみなので、これら3つを初期値として ret に追加します。
• n が偶数の場合は、空文字列を初期値として ret に追加します。

ステップ2：外側へ数字のペアを積み上げる

• n > 1 の間、n を2ずつ減らしながら以下の処理を繰り返します。
• 一時的な配列 temp を用意します。
• ret 内の各文字列 s について、左右対称になるよう数字のペアを前後に付加していきます。
• n > 3 のとき（まだ最上位桁を決めていない段階）は「0 + s + 0」も候補に加えます。先頭が0の数は有効な表記にならないため、最外周のペアでは「0」を使えない点に注意してください。
• 常に追加するのは「1 + s + 1」「8 + s + 8」「6 + s + 9」「9 + s + 6」の4パターンです。
• ループの最後で ret = temp と更新し、次の桁のペアへ進みます。

ステップ3：範囲内の個数をカウントする

• メイン側では、答えとなる ret を 0 で初期化します。
• low の桁数から high の桁数まで、各桁数 i について findStrobogrammatic(i) を呼び出して候補を取得します。
• 各候補 v[j] に対し、「v[j] が low 以上 かつ high 以下」を満たす場合のみカウントを1増やします。桁数が異なれば桁数だけで大小関係が確定し、同じ桁数なら文字列同士の辞書順比較で判定できるのがポイントです。
• 最終的な ret を返します。

C++による実装例

理解を深めるために、以下の実装コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
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;
    }
    bool compare(string a, string b){
        return a.size() == b.size() ? a >= b : a.size() > b.size();
    }
    int strobogrammaticInRange(string low, string high) {
        int ret = 0;
        vector<string> v;
        for (int i = low.size(); i <= high.size(); i++) {
            v = findStrobogrammatic(i);
            for (int j = 0; j < v.size(); j++) {
                ret += compare(v[j], low) && compare(high, v[j]);
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout <<(ob.strobogrammaticInRange("50", "100"));
}

入力例

"50","100"

出力例

3

計算量と実装のポイント

数字のペア1組につき最大5通り（0、1、8、6/9、9/6）の選択肢が増えるため、生成されるストロボグラム数の総数は桁数に対しておよそ指数的に増加します。そのため、この手法は low と high の桁数差が小さい場合に特に効率的に動作します。

また、候補を整数に変換せず文字列のまま比較している点も重要です。桁数が同じなら辞書順比較で大小が判定でき、桁数が異なれば長い方が大きいと決まるため、非常に大きな桁数の数値を扱ってもオーバーフローの心配がありません。