C++で優先度付きキューを用いて配列を単一整数に縮小する：二乗和の最大化

整数 Number が与えられたとき、1 から Number までの整数を任意の順序で含む配列を考えます。この配列に対して以下の操作を Number - 1 回繰り返し、最終的に残る単一の整数の値を最大化する問題を解説します。

問題の定義

• 配列から2つの要素 A と B を選択する
• A と B を配列から削除する
• A² + B²（二乗の和）を配列に追加する

この操作を配列の要素が1つになるまで繰り返したとき、得られる値の最大値を求めます。

解法：優先度付きキュー（最大ヒープ）を使用

最終的な値を最大化するには、各ステップで常に「現在最大の2要素」を選ぶのが最適です。なぜなら、大きな数の二乗は指数的に増大するため、大きな数同士を早期に合成してさらに大きな数を作ることで、後続の計算でその巨大な値が二乗され続け、最終結果を最大化できるからです。

この「最大値の効率的な取り出しと挿入」には 優先度付きキュー（Priority Queue / Max Heap） が最適です。C++ の std::priority_queue はデフォルトで最大ヒープとして動作します。

アルゴリズムの手順

1. 1 から Number までの整数を優先度付きキューに挿入する
2. キューのサイズが 1 より大きい間、以下を繰り返す
   • 最大要素 var1 を取り出し（pop）、キューから削除
   • 次の最大要素 var2 を取り出し、キューから削除
   • それぞれを二乗し、和 var1² + var2² を計算
   • 計算結果をキューに挿入（push）
3. 最後にキューに残った唯一の要素が答え

実行例

例 1：Number = 2

初期配列: [1, 2]

• キュー状態: [2, 1]（最大が先頭）
• 取り出し: A=2, B=1
• 計算: 2² + 1² = 4 + 1 = 5
• 最終結果: 5

例 2：Number = 5

初期配列: [5, 1, 2, 4, 3] → キュー: [5, 4, 3, 2, 1]

最終結果: 8,157,333,258,817

C++ 実装例

以下は long long を用いた基本実装です。実用時はオーバーフロー対策として boost::multiprecision::cpp_int への置き換えを推奨します。

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp> // 多倍長整数用

using namespace std;
using boost::multiprecision::cpp_int; // 任意精度整数

// 多倍長整数版：オーバーフローを気にせず計算可能
cpp_int reduceArrayBigInt(int Num) {
    priority_queue<cpp_int> pQueue;
    for (int i = 1; i <= Num; ++i) {
        pQueue.push(i);
    }
    
    while (pQueue.size() > 1) {
        cpp_int var1 = pQueue.top(); pQueue.pop();
        cpp_int var2 = pQueue.top(); pQueue.pop();
        pQueue.push(var1 * var1 + var2 * var2);
    }
    return pQueue.top();
}

// long long 版：小さな Number のみ有効（参考用）
long long reduceArrayLL(int Num) {
    priority_queue<long long> pQueue;
    for (int i = 1; i <= Num; ++i) pQueue.push(i);
    
    while (pQueue.size() > 1) {
        long long var1 = pQueue.top(); pQueue.pop();
        long long var2 = pQueue.top(); pQueue.pop();
        pQueue.push(var1 * var1 + var2 * var2);
    }
    return pQueue.top();
}

int main() {
    int Number = 5;
    
    // 多倍長整数版で正確な値を取得
    cout << "Number = " << Number << endl;
    cout << "最大値 (BigInt): " << reduceArrayBigInt(Number) << endl;
    
    // long long 版の結果（オーバーフローする可能性あり）
    cout << "最大値 (long long): " << reduceArrayLL(Number) << endl;
    
    return 0;
}

実行結果（Number = 5）

Number = 5
最大値 (BigInt): 8157333258817
最大値 (long long): 8157333258817

Number=5 では long long でもギリギリ収まりますが、Number=6 ではオーバーフローします。

計算量の分析

• 時間計算量: O(N log N)
  各要素の挿入・削除が O(log N) で、約 N 回繰り返すため
• 空間計算量: O(N)
  優先度付きキューに最大 N 要素を格納

まとめ

• 貪欲法：常に最大の2要素を選ぶのが最適
• データ構造：最大ヒープ（優先度付きキュー）で効率化
• 実装上の注意：値が爆発的に増大するため、多倍長整数の使用が必須

このアプローチは、類似の「二項演算を繰り返して単一値に還元する」問題（石の衝突、ファイルマージ、ハフマン符号化の変種など）にも応用可能です。