C++で解くn番目のスーパー・アグリー数（超醜い数）― 優先度付きキューを使った効率的な実装

スーパー・アグリー数とは？

スーパー・アグリー数（超醜い数）とは、そのすべての素因数が与えられた素数リスト primes（サイズ k）に含まれる正の整数のことです。

例えば、n = 12、primes = [2, 7, 13, 19] という条件の場合、出力は 32 になります。これは、[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] という並びが「12個目までのスーパー・アグリー数の列」に該当するためです。

本記事では、この問題を優先度付きキュー（最小ヒープ）を活用して効率よく解く方法を、C++のコード例とともに分かりやすく解説します。

解法のアプローチ

各素数ごとに「次の候補値（素数 × 既に確定したスーパー・アグリー数）」を管理し、ヒープによって常に最小の候補を取り出すのがポイントです。こうすることで、重複を排除しながら小さい順に数列を生成できます。

アルゴリズムの手順

1. num（候補値）、prime（素数）、idx（参照中のインデックス）の3つのフィールドを持つ構造体 Data を定義します。

2. n が 1 の場合は 1 を返します。そうでなければ、サイズ n+1 の配列 v を作成し、すべて 1 で初期化します。

3. 優先度付きキュー pq を定義します。

4. i を 0 から primes.size() − 1 までループし、各素数について Data(primes[i], primes[i], 2) を作成して pq に挿入します。

5. i を 2 から n まで以下を繰り返します：

   • pq の先頭要素を取り出して curr とし、キューから削除します。

   • val := curr.num とし、v[i] := val を代入します。

   • curr.num := curr.prime × v[curr.idx] を計算し、curr.idx を 1 増やしてから pq に戻します。

   • val == pq.top().num である限り、同じ処理を繰り返して重複する値を除去します。

6. v[n] を返します。

C++での実装例

以下の実装を見ると、処理の流れがより具体的につかめます。

#include <bits/stdc++.h>
using namespace std;
struct Data{
    int num, prime, idx;
    Data(int a, int b, int c){
        num = a;
        prime = b;
        idx = c;
    }
};
struct Comparator{
    bool operator()(Data a, Data b){
        return !(a.num < b.num);
    }
};
class Solution {
    public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if(n == 1)return 1;
        vector <int> v(n + 1, 1);
        priority_queue < Data, vector < Data >, Comparator > pq;
        for(int i = 0; i < primes.size(); i++){
            pq.push(Data(primes[i], primes[i], 2));
        }
        int x;
        for(int i = 2; i <= n; i++){
            Data curr = pq.top();
            pq.pop();
            int val = curr.num;
            v[i] = val;
            curr.num = curr.prime * v[curr.idx];
            curr.idx++;
            pq.push(curr);
            while(val == pq.top().num){
                curr = pq.top();
                pq.pop();
                curr.num = curr.prime * v[curr.idx];
                curr.idx++;
                pq.push(curr);
            }
        }
        return v[n];
    }
};
main(){
    Solution ob;
    vector<int> v = {2,7,13,19};
    cout << (ob.nthSuperUglyNumber(12, v));
}

入力

12
[2,7,13,19]

出力

32

計算量とまとめ

この手法では、各ステップで最大 k 個の要素に対するヒープ操作が発生するため、時間計算量は O(n·k·log k)、必要なメモリは配列とヒープの分だけなので空間計算量は O(n + k) となります。

単純な全探索（すべての数を素因数分解して判定する方法）では非常に非効率ですが、優先度付きキューを使うことで、素数リストのサイズや n が大きくなっても実用的な速度で n 番目のスーパー・アグリー数を求められます。「複数のポインタをヒープで統合管理する」という発想は、マージ系の問題全般にも応用できるテクニックなので、ぜひ覚えておきましょう。