C++で数値Nを回文の和として表すために必要な最小の回文の個数を求める方法

問題の概要

数値Nが与えられたとき、Nをいくつかの回文（上から読んでも下から読んでも同じ並びになる数）の和として表すために必要な回文の最小個数を求める問題です。

例えば、N = 15の場合、15 = 8 + 7 と表現できるため、必要な回文の個数は2となります。

アルゴリズムの考え方

この問題は次の2つのステップで解くことができます。

1. N以下のすべての回文を昇順に生成する
2. 和がちょうどNになるような最小の部分集合のサイズを求める

後半のステップはいわゆる「部分和問題」の一種であり、メモ化再帰（動的計画法）を用いることで効率的に解けます。

回文の効率的な生成方法

すべての数値に対して回文かどうかを1つずつ判定するのではなく、前半部分の数値を決め、その数字列を反転させて後半を構築する方法が効率的です。桁数が奇数の場合は中央の1桁を共有し、偶数の場合は前半をそのまま反転して結合します。

C++による実装例

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
vector<vector<long long>> table;
int createPalindrome(int input, bool isOdd){
    int n = input;
    int palindrome = input;
    if (isOdd)
        n /= 10;
    while (n > 0) {
        palindrome = palindrome * 10 + (n % 10);
        n /= 10;
    }
    return palindrome;
}
vector<int>generatePalindromes(int n){
    vector<int> palindromes;
    int number;
    for (int j = 0; j < 2; j++) {
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= n)
            palindromes.push_back(number);
    }
    return palindromes;
}
long long minSubsetSize(vector<int>& vec, int i, int j, int n){
    if (n == 0)
    return 0;
    if (i > j || vec[i] > n)
    return INT_MAX;
    if (table[i][n])
    return table[i][n];
    table[i][n] = min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]), minSubsetSize(vec, i + 1, j, n));
    return table[i][n];
}
int requiredPalindromes(int n){
    vector<int> palindromes = generatePalindromes(n);
    sort(palindromes.begin(), palindromes.end());
    table = vector<vector<long long>>(palindromes.size(),
    vector<long long>(n + 1, 0));
    return minSubsetSize(palindromes, 0, palindromes.size() - 1, n);
}
int main(){
    int n = 15;
    cout << "Minimum required palindromes = " <<
    requiredPalindromes(n) << endl;
    return 0;
}

コードの解説

• createPalindrome関数：前半部分の数値を受け取り、それを反転して結合することで回文を生成します。引数isOddがtrueの場合は奇数桁の回文（中央の桁を共有）、falseの場合は偶数桁の回文を生成します。
• generatePalindromes関数：奇数桁・偶数桁の両方のパターンについて、N以下のすべての回文を生成してベクターに格納します。
• minSubsetSize関数：メモ化再帰により、i番目以降の回文を使って和をnにするのに必要な最小個数を計算します。2次元配列tableに計算結果をキャッシュすることで、同じ状態の再計算を防いでいます。
• requiredPalindromes関数：回文の生成・ソート、メモ化テーブルの初期化を行い、最終的な答えを返します。

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required palindromes = 2

計算量について

生成される回文の個数をPとすると、時間計算量・空間計算量はいずれもO(P × N)となります。桁数dの回文の個数はおよそ10のd/2乗程度に収まるため、Nがそこまで大きくない場合は十分に高速に動作します。