C++でサイズKの部分集合の積に含まれる末尾ゼロの最大数を求める方法

本記事では、サイズ N の配列から選ぶサイズ K の部分集合の積において、末尾に連続する 0（末尾ゼロ）の数が最大となる値を求める問題を解説します。

問題の例

入力 − Arr[] = {5, 20, 2}、K = 2

出力 − 2

説明 − サイズ 2 の部分集合は全部で 3 つ作成できます。

[5, 20] の積は 100 です。
[20, 2] の積は 40 です。
[5, 2] の積は 10 です。

100 の末尾ゼロの数が最も多く、その数は 2 です。したがって答えは 2 となります。

入力 − Arr[] = {60, 40, 25}、K = 2

出力 − 3

解法の考え方：なぜ 2 と 5 なのか？

数の末尾に付く 0 の個数は、その数に含まれる因数 10 の個数と一致します。10 = 2 × 5 であるため、積に含まれる「2 の個数」と「5 の個数」のうち小さい方が末尾ゼロの数になります。そこで、各要素を 2 と 5 で割れるだけ割って指数をカウントし、動的計画法（DP）で「5 の個数ごとの 2 の個数の最大値」を管理します。

プログラムで使用しているアプローチ

• 関数を始める前に、#define M5 100 を先頭で定義します。
• MaxZeros() 関数内で、2 次元配列 Sub[K + 1][M5 + 5] を作成し、すべての値を -1 で初期化した上で、Sub[0][0] = 0 を設定します。
• P = 0 から P < N までループし、ループ内で int 型の P2 と P5 を初期化します。これらはそれぞれ、対象の数に含まれる 2 の個数と 5 の個数を格納するために使用します。
• while (Arr[P] % 2 == 0) を条件とする while ループを開始し、ループ内で P2++ と Arr[P] /= 2 を実行して 2 の個数を求めます。P5 についても同様の手順を繰り返します。
• 続いて、上記の for ループ内に、さらに 2 つのネストされた for ループを以下のように配置します。
  for (int i = K - 1; i >= 0; i--)
  for (int j = 0; j < M5; j++)
• これらのループ内で if (Sub[i][j] != -1) を判定し、真であれば Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2); を実行します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
    // すべての値を -1 で初期化
    int Sub[K+1][M5+5];
    memset(Sub, -1, sizeof(Sub));
    Sub[0][0] = 0;
    for (int P = 0; P < N; P++){
        int P2 = 0, P5 = 0;
        // Arr[P] に含まれる 2 の最大べき乗数
        while (Arr[P] % 2 == 0){
            P2++;
            Arr[P] /= 2;
        }
        // Arr[P] に含まれる 5 の最大べき乗数
        while (Arr[P] % 5 == 0) {
            P5++;
            Arr[P] /= 5;
        }
        /* 先頭の i 個の数を調べ、5 の総べき乗数が j となる組み合わせから 2 を収集 */
        for (int i = K - 1; i >= 0; i--)
            for (int j = 0; j < M5; j++)
            // Sub[i][j] が未計算の場合
            if (Sub[i][j] != -1)
                Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
    }
    /* 5 または 2 の最小値を取り、結果を最大化 */
    int ans = 0;
    for (int i = 0; i < M5; i++)
    ans = max(ans, min(i, Sub[K][i]));
    return ans;
}
// メイン関数
int main(){
    int Arr[] = { 60, 40, 25 };
    int K = 2;
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << MaxZeros(Arr, N, K);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます −

3

まとめ

この問題は、「末尾ゼロの数が 2 と 5 のペアの個数で決まる」という性質を利用することで効率的に解けます。DP テーブルの行を「選んだ要素の数」、列を「5 の総べき乗数」とすることで、サイズ K の部分集合の中で min(2 の個数, 5 の個数) を最大化でき、計算量 O(N × K × M5) で答えを導出できます。