C++で多項式の根の和を最小化する

整数の配列が与えられ、これが多項式の係数を表しているとします。配列のサイズは'n'、つまり要素数です。多項式の次数は常に n-1 になります（末尾が定数項になるため）。この係数を並べ替えて、多項式の根の和を最小化するのが課題です。

入力と出力の例

例 1

入力: int arr[] = { 2, -1, 4, 9, -1, 10, -5 }

出力: Minimize the sum of roots of a given polynomial is: -1 -5 2 4 9 -1 10

解説: 要素数7の配列なので、多項式の次数は6次です。並べ替え後の多項式は以下のようになります。
-1 * x^6 - 5 * x^5 + 2 * x^4 + 4 * x^3 + 9 * x^2 - 1 * x^1 + 10
これにより根の和が最小化され、-5 と 1 となります。

例 2

入力: int arr[] = {3, -2, -1, 4}

出力: Minimize the sum of roots of a given polynomial is: -1 -2 3 4

解説: 要素数4の配列なので、多項式の次数は3次です。並べ替え後の多項式は以下のようになります。
-1 * x^3 - 2 * x^2 + 3 * x^1 + 4
これにより根の和が最小化され、-1 となります。

アルゴリズムのアプローチ

1. 整数配列を入力し、サイズを取得して処理関数に渡します。
2. 関数 Minimize_root 内で以下の処理を行います。
   • 3つのベクター vec_1（結果用）、vec_2（正の係数のインデックス）、vec_3（負の係数のインデックス）を宣言します。
   • 配列を走査し、正の値のインデックスを vec_2、負の値のインデックスを vec_3 に格納します。
   • 正・負それぞれの要素数が2以上の場合、以下の戦略で並べ替えを行います。
     • 正の係数から最大値と最小値（最大値と異なるインデックス）を探します。
     • 負の係数から絶対値の最大値と最小値（最大値と異なるインデックス）を探します。
     • 正の係数ペアの比 -max_val / min_val と、負の係数ペアの比 -abs_max / abs_min を比較します。
     • より小さい比を持つペアを結果の先頭2要素として配置し、残りの要素を元の順序で追加します。
   • 正の係数のみ2以上の場合、正の係数ペアで同様の処理を行います。
   • 負の係数のみ2以上の場合、負の係数ペアで同様の処理を行います。
   • どちらも2未満の場合は「Not Possible」と出力します。

C++ 実装例

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

void Minimize_root(int arr[], int size) {
    vector<int> vec_1; // 結果格納用
    vector<int> vec_2; // 正の係数のインデックス
    vector<int> vec_3; // 負の係数のインデックス

    // 正負でインデックスを分離
    for (int i = 0; i < size; i++) {
        if (arr[i] > 0) {
            vec_2.push_back(i);
        } else if (arr[i] < 0) {
            vec_3.push_back(i);
        }
    }

    int vec_2_size = vec_2.size();
    int vec_3_size = vec_3.size();

    // 正負両方とも2個以上ある場合
    if (vec_2_size >= 2 && vec_3_size >= 2) {
        int max_val = INT_MIN, temp = -1;
        int min_val = INT_MAX, temp_2 = -1;
        int N_max = INT_MIN, N_temp = -1;
        int N_min = INT_MAX, N_temp_2 = -1;

        // 正の係数: 最大値の探索
        for (int i = 0; i < vec_2_size; i++) {
            if (arr[vec_2[i]] > max_val) {
                temp = vec_2[i];
                max_val = arr[temp];
            }
        }
        // 正の係数: 最小値の探索（最大値と異なるインデックス）
        for (int i = 0; i < vec_2_size; i++) {
            if (arr[vec_2[i]] < min_val && vec_2[i] != temp) {
                temp_2 = vec_2[i];
                min_val = arr[temp_2];
            }
        }
        // 負の係数: 絶対値最大値の探索
        for (int i = 0; i < vec_3_size; i++) {
            if (abs(arr[vec_3[i]]) > N_max) {
                N_temp = vec_3[i];
                N_max = abs(arr[N_temp]);
            }
        }
        // 負の係数: 絶対値最小値の探索（最大値と異なるインデックス）
        for (int i = 0; i < vec_3_size; i++) {
            if (abs(arr[vec_3[i]]) < N_min && vec_3[i] != N_temp) {
                N_temp_2 = vec_3[i];
                N_min = abs(arr[N_temp_2]);
            }
        }

        // 比較してより良い方を選択
        double vec_2_data = -1.0 * max_val / min_val;
        double vec_3_data = -1.0 * N_max / N_min;

        if (vec_2_data < vec_3_data) {
            vec_1.push_back(arr[temp_2]);
            vec_1.push_back(arr[temp]);
            for (int i = 0; i < size; i++) {
                if (i != temp_2 && i != temp) vec_1.push_back(arr[i]);
            }
        } else {
            vec_1.push_back(arr[N_temp_2]);
            vec_1.push_back(arr[N_temp]);
            for (int i = 0; i < size; i++) {
                if (i != N_temp_2 && i != N_temp) vec_1.push_back(arr[i]);
            }
        }
    }
    // 正の係数のみ2個以上の場合
    else if (vec_2_size >= 2) {
        int max_val = INT_MIN, temp = -1;
        int min_val = INT_MAX, temp_2 = -1;
        for (int i = 0; i < vec_2_size; i++) {
            if (arr[vec_2[i]] > max_val) {
                temp = vec_2[i];
                max_val = arr[temp];
            }
        }
        for (int i = 0; i < vec_2_size; i++) {
            if (arr[vec_2[i]] < min_val && vec_2[i] != temp) {
                temp_2 = vec_2[i];
                min_val = arr[temp_2];
            }
        }
        vec_1.push_back(arr[temp_2]);
        vec_1.push_back(arr[temp]);
        for (int i = 0; i < size; i++) {
            if (i != temp_2 && i != temp) vec_1.push_back(arr[i]);
        }
    }
    // 負の係数のみ2個以上の場合
    else if (vec_3_size >= 2) {
        int N_max = INT_MIN, temp = -1;
        int N_min = INT_MAX, temp_2 = -1;
        for (int i = 0; i < vec_3_size; i++) {
            if (abs(arr[vec_3[i]]) > N_max) {
                temp = vec_3[i];
                N_max = abs(arr[temp]);
            }
        }
        for (int i = 0; i < vec_3_size; i++) {
            if (abs(arr[vec_3[i]]) < N_min && vec_3[i] != temp) {
                temp_2 = vec_3[i];
                N_min = abs(arr[temp_2]);
            }
        }
        vec_1.push_back(arr[temp_2]);
        vec_1.push_back(arr[temp]);
        for (int i = 0; i < size; i++) {
            if (i != temp_2 && i != temp) vec_1.push_back(arr[i]);
        }
    } else {
        cout << "Not Possible";
        return;
    }

    // 結果出力
    for (int val : vec_1) {
        cout << val << " ";
    }
}

int main() {
    int arr[] = { 2, -1, 4, 9, -1, 10, -5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimize the sum of roots of a given polynomial is: ";
    Minimize_root(arr, size);
    return 0;
}

実行結果

Minimize the sum of roots of a given polynomial is: -1 -5 2 4 9 -1 10