C++で解くConfusing Number II：180度回転すると別の数になる「紛らわしい数」の個数を求める

問題の概要

ある数字を180度回転させると、別の数字へと変化することがあります。具体的には、0、1、6、8、9を180度回転すると、それぞれ0、1、9、8、6になります。一方で、2、3、4、5、7は回転させると無効な数字になってしまいます。

この性質を使った「紛らわしい数（Confusing Number）」とは、180度回転させると元の数とは異なる新しい数になる数のことです。正の整数Nが与えられたとき、1以上N以下の範囲に存在する紛らわしい数の個数を求めるのがこの問題です。

例えば、入力が20の場合、出力は6となります。これは、6→9、9→6、10→1、16→91、18→81、19→61 の6つが条件を満たすためです。

解法の考え方

この問題は、有効な数字（0、1、6、8、9）だけを使って数を構築しながら、同時にその回転後の値も追跡することで効率的に解けます。すべての数を順番に調べるのではなく、DFS（深さ優先探索）による再帰的な構築がポイントです。

アルゴリズムの手順

• 回転後の対応関係を保持するマップ mapping を定義する
• 使用可能な数字を格納する配列 valid = {0, 1, 6, 8, 9} を用意する
• 引数に num（現在の数）、rotate（回転後の数）、digit（次の桁の重み）、N を取る関数 solve() を定義する
• rotate != num の場合、その数は紛らわしい数なので ret を1増やす
• valid の各数字 dig について以下を繰り返す：
  • num * 10 + dig > N ならばループを抜ける
  • そうでなければ solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N) を再帰呼び出しする

メイン処理の流れ

• カウンタ ret を 0 で初期化する
• マッピングを設定する：0→0、1→1、6→9、9→6、8→8
• 先頭の桁が0にならないように、1、6、9、8 を先頭とした4つの再帰呼び出しを実行する
• 最後に ret を返す

C++実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int ret;
    map<int, int> mapping;
    vector<int> valid;
    void solve(lli num, lli rotate, lli digit, lli N){
        if (rotate != num) {
            ret++;
        }
        for (int i = 0; i < valid.size(); i++) {
            int dig = valid[i];
            if (num * 10 + dig > N) {
                break;
            }
            solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N);
        }
    }
    int confusingNumberII(int N) {
        ret = 0;
        valid = { 0, 1, 6, 8, 9 };
        mapping[0] = 0;
        mapping[1] = 1;
        mapping[6] = 9;
        mapping[9] = 6;
        mapping[8] = 8;
        solve(1, 1, 10, N);
        solve(6, 9, 10, N);
        solve(9, 6, 10, N);
        solve(8, 8, 10, N);
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.confusingNumberII(20));
}

実行結果

入力

20

出力

6

ポイントのまとめ

このアルゴリズムの計算量は、生成される候補の数に依存します。各桁で使える数字は最大5種類しかないため、Nがd桁の場合の探索対象は最大でも5^d個程度にとどまり、単純な全数走査（O(N)）よりもはるかに高速です。

また、回転後の数は下の桁から積み上がっていくため、mapping[dig] * digit + rotate という式で現在の回転値を更新しています。この工夫により、数を構築しながら同時に回転後の値も計算でき、文字列への変換などの余分な処理が不要になっています。