C++で複数の合計操作によりターゲット配列を構築できるか判定する方法

整数型の配列 target が与えられているとします。ここで、すべての要素が 1 である初期配列 A から出発し、次の手順を実行することができます。

• 現在配列に含まれる全要素の合計を x とします。
• 0 以上 n 以下の範囲(n は配列のサイズ)からインデックス i を選択し、A の i 番目の要素の値を x に置き換えます。
• この手順は必要な回数だけ何度でも繰り返せます。

このとき、初期配列 A からターゲット配列を作成することが可能かどうかを判定してください。不可能な場合は false を返します。

例えば、入力が [3,9,5] の場合、答えは true になります。手順は以下の通りです。

• 初期状態は [1,1,1] です。
• 合計は 3 なので、インデックス 0 に書き込み、配列は [3,1,1] になります。
• 合計は 5 なので、インデックス 2 に書き込み、配列は [3,1,5] になります。
• 合計は 9 なので、インデックス 1 に書き込み、配列は [3,9,5] となり、目標に到達します。

解決のためのアプローチ

この問題は、逆算的な思考が鍵となります。ターゲット配列の中で最も大きい値は、直前の操作で必ず「合計値が書き込まれた」場所です。つまり、最大値を現在の合計で引き戻すことで、ひとつ前の状態へ復元できます。これを効率的に行うために優先度付きキュー(priority queue)を使用します。

具体的には、次の手順で判定を行います。

• sum := 0 とし、target のサイズを n とします。
• i := 0 から n 未満までループし、sum に target[i] を加算していきます。
• target 配列全体で優先度付きキュー pq を初期化します。
• pq の先頭要素 × 2 が sum より大きい間、次を繰り返します。
  • x := pq の先頭要素
  • pq から先頭要素を削除
  • pq に (2 * x − sum) を挿入
  • sum := x と更新
• 最終的に sum が target のサイズと一致すれば true、そうでなければ false を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool isPossible(vector<int>& target) {
        lli sum = 0;
        int n = target.size();
        for (int i = 0; i < n; i++) {
            sum += target[i];
        }
        priority_queue<int> pq(target.begin(), target.end());
        while (pq.top() * 2 > sum) {
            int x = pq.top();
            pq.pop();
            pq.push(2 * x - sum);
            sum = x;
        }
        return sum == (int)target.size();
    }
};
main(){
    Solution ob;
    vector<int> v = {3,9,5};
    cout << (ob.isPossible(v));
}

入力

{3,9,5}

出力

1

補足：計算量について

このアルゴリズムでは、各ステップで最大値を取り出して逆算処理を行うため、優先度付きキューの操作あたり O(log n) のコストがかかります。全体の計算量は O(n log n + k log n)(k は逆算の繰り返し回数)であり、大きな入力に対しても効率的に動作します。また、合計値のオーバーフローを防ぐため、long long 型(lli)を使用している点にも注目してください。