【C++】与えられた2つの方程式を満たすN個の正の整数を見つける方法

この問題では、3つの値 A、B、N が与えられ、与えられた2つの方程式を同時に満たすN個の正の整数を見つけることが求められます。

問題の概要

以下の2つの条件を同時に満たすN個の正整数 x₁, x₂, …, xₙ を見つけます。

x12 + x22 + … + xn2 ≥ A
x1 + x2 + … + xn ≤ B

条件を満たす組み合わせが存在する場合はそのN個の値を出力し、存在しない場合は -1 を出力します。

入出力例で問題を理解しよう

入力

N = 4, A = 65, B = 16

出力

1 1 1 8

説明

出力された値は、次のように両方の条件を満たしています。

12 + 12 + 12 + 82 = 1 + 1 + 1 + 64 = 67 ≥ 65
1 + 1 + 1 + 8 = 11 < 16

解法アプローチ

この問題に対するシンプルな解法は、「二乗和を最大化する」という発想です。関数 f(x) = x² は凸関数であるため、合計が一定のとき、値をできるだけ偏らせるほど二乗和は大きくなります。

そこで、N個のうち1つの数をできるだけ大きく(B − (N−1))取り、残りの N−1 個はすべて 1 にします。こうすることで、「合計がB以下」という制約を守りながら二乗和を最大化できます。得られた二乗和がA以上であれば答えが存在し、A未満であればどのような組み合わせでも条件を満たせないため -1 を出力します。

実装例(C++)

以下は、この解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;

void findNintegers(int N, int A, int B) {
    vector<int> numbers;
    // 残りの N-1 個を 1 で初期化
    for (int i = 0; i < N - 1; i++)
        numbers.push_back(1);
    // 最後の1つを大きく取れない場合は解なし
    if (B - (N - 1) <= 0) {
        cout << "-1";
        return;
    }
    numbers.push_back(B - (N - 1));
    // 二乗和を計算
    int vals = 0;
    for (int i = 0; i < N; i++)
        vals += numbers[i] * numbers[i];
    // 二乗和が A 未満なら条件を満たせない
    if (vals < A) {
        cout << "-1";
        return;
    }
    for (int i = 0; i < N; i++)
        cout << numbers[i] << " ";
}

int main(){
    int N = 4, A = 65, B = 17;
    cout<<N<<" positive integers that satisfy the given equations are ";
    findNintegers(N, A, B);
    return 0;
}

出力

4 positive integers that satisfy the given equations are 1 1 1 14

計算量の評価

時間計算量: O(N) ― 数列の生成と二乗和の計算に、それぞれ要素数に比例した時間しかかかりません。
空間計算量: O(N) ― N個の整数を格納するためのベクターが必要です。

このように、凸関数の性質を利用した貪欲な構成により、非常に効率的に解を求めることができます。