C++で解く：配列の要素を反転して得られる異なる値の最大数を求めるアルゴリズム

n個の要素を持つ配列Aがあるとします。与えられた数値の中から任意の部分集合を選び、それらの数値の符号を反転（マイナスに変更）することができます。このとき、配列内に作り出せる異なる値の最大数を求めるのがこの問題です。

例えば、入力が A = [1, 1, 2, 2] の場合、出力は 4 になります。これは、最初と最後の数値の符号を反転することで、配列 [-1, 1, 2, -2] を作り、4つの異なる値が得られるためです。

解法のアプローチ

この問題は、セット（set）を使うことでシンプルに解くことができます。考え方のポイントは次の通りです。

• 各要素について、その値がすでにセットに存在するかどうかを確認します。
• まだ存在しない場合は、元の値（x）をセットに挿入します。
• すでに存在する場合（重複している場合）は、符号を反転した値（-x）をセットに挿入します。
• 最終的なセットのサイズが、求める「異なる値の最大数」となります。

この貪欲法（グリーディー）の戦略により、値 x とその反転値 -x を両方セットに含められる可能性が最大化されます。なお、0の場合は反転しても0のままであるため、自動的に正しく処理されます。

手順の擬似コード

セット se を定義する
n := A のサイズ
i := 0 から i < n の間、i を 1 ずつ増やしながら繰り返す：
　　x := A[i]
　　もし x が se に存在するなら：
　　　　-x を se に挿入する
　　そうでなければ：
　　　　x を se に挿入する
se のサイズを返す

C++での実装例

以下に、実際のC++コードによる実装を示します。

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

int solve(vector<int> A) {
    set<int> se;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        int x = A[i];
        if (se.count(x))
            se.insert(-x);
        else
            se.insert(x);
    }
    return se.size();
}

int main() {
    vector<int> A = { 1, 1, 2, 2 };
    cout << solve(A) << endl;
}

入力

{ 1, 1, 2, 2 }

出力

4

計算量について

このアルゴリズムでは、各要素に対してセットへの検索と挿入を行います。std::set は平衡二分探索木で実装されているため、1回の操作あたり O(log n) の計算量が必要です。したがって、全体の時間計算量は O(n log n)、空間計算量は O(n) となります。