C++で配列の積が元より大きくなるように全要素に割り当てる最小値を求める方法

問題の概要

n個の要素からなる配列が与えられたとします。配列のすべての要素をある最小値xに更新し（arr[i] = x）、新しい配列の全要素の積が、元の配列の全要素の積よりも厳密に大きくなるようにします。ここで、1 <= n <= 10^5、1 <= arr[i] <= 10^10 という制約が課せられています。

例えば、配列が [4, 2, 1, 10, 6] の場合を考えてみましょう。このとき答えは4になります。実際に、4 × 4 × 4 × 4 × 4 = 1024 となり、元の積 4 × 2 × 1 × 10 × 6 = 480 よりも大きくなることが確認できます。

アプローチ：対数を利用したn乗根の計算

n個の要素の積をPとすると、求めるべき値xはPのn乗根に相当します。しかし、各要素が最大10^10までの値を取りうるため、積Pは膨大な数になり、直接計算するのは現実的ではありません。

そこで対数（log）を活用します。積のn乗根を求めるには、以下の手順に従います。

1. 配列の各要素の対数（底10）を計算し、その合計を求める
2. 合計を要素数nで割る
3. その結果の逆対数（antilog）を計算し、切り上げ（ceil）を行う

数式で表すと次のようになります。

res = ceil(10 ^ (Σ log10(arr[i]) / n))

浮動小数点演算の誤差を避けるため、実装では微小な定数EPS（1e-15）を加えて精度を確保しています。

C++による実装例

#include <iostream>
#include <cmath>
#define EPS 1e-15
using namespace std;
long long findMinValue(long long arr[], long long n) {
    long double sum = 0;
    for (int i = 0; i < n; i++)
        sum += (long double)log10(arr[i]) + EPS;
    long double xl = (long double)(sum / n + EPS);
    long double res = pow((long double)10.0, (long double)xl) + EPS;
    return (long long)ceil(res + EPS);
}
int main() {
    long long arr[] = {4, 2, 1, 10, 6};
    long long n = sizeof(arr) / sizeof(arr[0]);
    cout << "Min value is: " << findMinValue(arr, n);
}

出力結果

Min value is: 4

計算量の評価

このアルゴリズムは配列を一度走査するだけなので、時間計算量はO(n)、使用する追加メモリは定数のみでO(1)となります。nが最大10^5の大規模な配列でも、積を直接計算することなくオーバーフローを回避しながら高速に最小値を求められる点が、この対数ベースのアプローチの大きな利点です。