C++でn番目の醜い数（Ugly Number）を求めるプログラム【動的計画法】

整数 n が与えられたとき、n番目の「醜い数（Ugly Number）」を求めることを考えます。醜い数とは、その素因数が 2、3、5 のみである数のことです。例えば、10番目の醜い数は 12 になります。小さい方から順に並べると、1、2、3、4、5、6、8、9、10、12、… となるためです。

この問題は、動的計画法を用いることで効率的に解くことができます。基本となる発想は、「すでに求めた醜い数に 2、3、5 を掛けた値もまた醜い数になる」という性質を利用し、重複なく小さい順に次の醜い数を生成していくというものです。

アルゴリズムの手順

• (n + 1) サイズの配列 v を定義します。
• n が 1 の場合は 1 を返します。
• 候補値として two := 2、three := 3、five := 5 を初期化します。
• インデックスとして twoIdx := 2、threeIdx := 2、fiveIdx := 2 を初期化します。
• i := 2 から n まで、以下を繰り返します。
  • curr := two、three、five の中で最も小さい値とします。
  • v[i] := curr とします。
  • curr が two と等しい場合：two := v[twoIdx] × 2 とし、twoIdx を 1 増やします。
  • curr が three と等しい場合：three := v[threeIdx] × 3 とし、threeIdx を 1 増やします。
  • curr が five と等しい場合：five := v[fiveIdx] × 5 とし、fiveIdx を 1 増やします。
• 最後に v[n] を返します。

ここで重要なのは、curr が複数の候補と一致した場合（例：6 = 2×3）、該当するすべてのインデックスを進める点です。これにより、同じ数が配列に重複して登録されるのを防げます。このアルゴリズムの計算量は O(n)、必要な空間も O(n) で済みます。

C++での実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int nthUglyNumber(int n) {
        vector<int> v(n + 1);
        if(n == 1){
            return 1;
        }
        int two = 2, three = 3, five = 5;
        int twoIdx = 2;
        int threeIdx = 2;
        int fiveIdx = 2;
        for(int i = 2; i <= n; i++){
            int curr = min({two, three, five});
            v[i] = curr;
            if(curr == two){
                two = v[twoIdx] * 2;
                twoIdx++;
            }
            if(curr == three){
                three = v[threeIdx] * 3;
                threeIdx++;
            }
            if(curr == five){
                five = v[fiveIdx] * 5;
                fiveIdx++;
            }
        }
        return v[n];
    }
};

int main(){
    Solution ob;
    cout << ob.nthUglyNumber(15);
}

入力

15

出力

24

このプログラムでは、15番目の醜い数として 24 が出力されます。15番目までの醜い数は 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24 であり、確かに15番目が 24 になっていることが確認できます。