C++で解くスーパーパリンドローム ― 区間内の「回文の平方数」を効率的に数える

正の整数 N がスーパーパリンドローム（superpalindrome）であるとは、次の2つの条件を同時に満たすことを指します。

• N 自身が回文である（前から読んでも後ろから読んでも同じ数になる）

• N が「ある回文の平方」である（つまり N = k² となる k 自身も回文である）

本記事では、2つの正の整数 L と R が与えられたとき、閉区間 [L, R] に含まれるスーパーパリンドロームの個数を求める問題を、C++ の実装例とともにわかりやすく解説します。

たとえば、入力が L = 5、R = 500 の場合、出力は 3 となります。この範囲に含まれるスーパーパリンドロームは 9（=3²）、121（=11²）、484（=22²） の3つです。

解法のアプローチ

区間内のすべての整数を一つひとつ調べると計算量が膨大になってしまいます。そこで本手法では、「回文になりうる数の候補だけを再帰的に生成し、その平方が回文になっているかどうかのみを検証する」という効率的な戦略を採用します。こうすることで探索対象を大幅に絞り込め、高速に答えを求められます。

helper 関数の定義

再帰探索の中核となる関数 helper(x, m, M, lb, ub) を定義します。引数はそれぞれ、現在生成中の回文候補 x、現在の桁数 m、最大桁数 M、下限 lb、上限 ub を表します。処理の流れは以下のとおりです。

• x > ub の場合：

  • これ以上桁を増やしても範囲外になるため、探索を打ち切って return します。

• x ≥ lb かつ x × x が回文の場合：

  • 条件を満たすスーパーパリンドロームが見つかったので、答え ans を1つ増やします。

• i を 1 から順に増やしながら、m + 2×i ≤ M を満たす間、以下を繰り返します。

  • W := 10^{m + 2×i − 1} + 1（両端に新しい数字を配置するための重み）

  • w := 10ⁱ（既存の桁をずらすための重み）

  • z を 1 から 9 まで動かしながら、helper(z × W + x × w, m + 2×i, M, lb, ub) を再帰的に呼び出します。これにより、現在の候補 x の前後に同じ数字 z を追加した新しい回文候補が生成されます。

メイン処理の流れ

1. lb := √L、ub := √R を求めます（回文の平方根を探す探索範囲となります）。
2. M := log₁₀(ub) + 1 を計算し、ub の桁数を取得します。
3. z を 0 から 9 まで動かしながら、helper(z, 1, M, lb, ub) と helper(11 × z, 2, M, lb, ub) を呼び出して探索を開始します（1桁および2桁の回文を種として設定しています）。
4. 最後に ans を返します。

それでは、以下の実装例を見ながら理解を深めましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
    int ans = 0;
    public:
    int superpalindromesInRange(string L, string R){
        long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
        int M = log10l(ub) + 1;
        for (int z = 0; z <= 9; z++) {
            helper(z, 1, M, lb, ub);
            helper(11 * z, 2, M, lb, ub);
        }
        return ans;
    }
    private:
    void helper(long x, int m, int M, long double lb, long double ub){
        if (x > ub)
        return;
        if (x >= lb && is_palindrome(x * x))
        ans++;
        for (int i = 1; m + 2 * i <= M; i++) {
            long W = powl(10, m + 2 * i - 1) + 1;
            long w = powl(10, i);
            for (int z = 1; z <= 9; z++)
            helper(z * W + x * w, m + 2 * i, M, lb, ub);
        }
    }
    bool is_palindrome(long x){
        if (x == 0)
        return true;
        if (x % 10 == 0)
        return false;
        long left = x, right = 0;
        while (left >= right) {
            if (left == right || left / 10 == right)
            return true;
            right = 10 * right + (left % 10), left /= 10;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.superpalindromesInRange("5", "500"));
}

補助関数 is_palindrome() は、数値を文字列化せずに半分だけ反転させることで、効率よく回文判定を行っています。また、末尾が 0 の数は回文になりえないため、早期に除外している点もポイントです。

入力

"5", "500"

出力

3