C++で暗号化配列（他の要素の合計からなる配列）から元の配列を復元する方法

整数の配列が与えられ、この配列が「暗号化された配列」であるとします。例えば、暗号化配列が A = [10, 14, 12, 13, 11] で、元の配列が B = [5, 1, 3, 2, 4] だったとしましょう。このとき、配列 A の各要素 A[i] は次の規則に従っています。

A[i] = 元の配列 B における、自分自身（B[i]）を除くすべての要素の合計

この記事では、このような暗号化された配列から、元の配列を効率的に復元する方法を解説します。

解法の考え方：算術的な観察

この問題は、シンプルな算術的な性質に基づいて解くことができます。まず、配列のサイズを 4 と仮定し、元の配列を B = [a, b, c, d] とします。すると、暗号化配列 A は次のようになります。

A = [b+c+d, a+c+d, a+b+d, a+b+c]

ここで、A のすべての要素を足し合わせてみましょう。

sum = (b+c+d) + (a+c+d) + (a+b+d) + (a+b+c) = 3 × (a+b+c+d)

つまり、A の総和は「元の配列 B の総和 × (n−1)」と一致します。したがって、B の総和は sum / (n−1) で求められます（サイズ 4 の場合は sum / 3）。

あとは、元の配列の各要素を次の式で復元できます。

B[i] = Bの総和 − A[i]

この例では、B = [sum − A[0], sum − A[1], sum − A[2], sum − A[3]] となります。

C++での実装例

#include<iostream>
using namespace std;

void showOriginalArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    sum = sum / (n - 1); // 元の配列の総和を求める
    for (int i = 0; i < n; i++)
        cout << (sum - arr[i]) << " ";
}

int main() {
    int arr[] = {10, 14, 12, 13, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    showOriginalArray(arr, n);
}

出力

5 1 3 2 4

アルゴリズムのポイント

このアルゴリズムの流れは以下の通りです。

1. 暗号化配列 A の総和を計算する。
2. 総和を (n−1) で割り、元の配列 B の総和を求める。
3. 各要素について「Bの総和 − A[i]」を計算し、元の配列を復元する。

計算量は配列を2回走査するだけなので、時間計算量 O(n)、空間計算量 O(1) と非常に効率的です。

注意点： 配列のサイズ n が 1 の場合、(n−1) による除算が発生するため、この手法は n ≥ 2 の配列にのみ適用できます。また、要素が整数の場合、総和が (n−1) で割り切れることを前提とするため、実際の入力データがこの性質を満たしているか確認しておくと安全です。