配列Aから隠れた配列Bを復元するC++コードの解説

問題の概要

n 個の要素を持つ配列 A が与えられ、同じサイズ n の隠れた配列 B が存在するとします。B の要素は正にも負にもなり得ます。各インデックス i（1 から n までの範囲）に対して、次の操作が実行された結果が配列 A に格納されています。

• まず A[i] を 0 に初期化する
• その後、B[i] を加算し、B[i+1] を減算し、さらに B[i+2] を加算する、という操作を交互に繰り返す

つまり、A[i] = B[i] − B[i+1] + B[i+2] − B[i+3] + … という関係が成り立っています。このとき、元の配列 B を復元することが課題となります。

例えば、入力が A = [6, -4, 8, -2, 3] の場合、出力は [2, 4, 6, 1, 3] となります。

解法のアプローチ

この問題を解く鍵は、隣り合う要素同士の和に注目することです。A[i] と A[i+1] の定義式を足し合わせると、交互に現れる符号が打ち消し合い、次のシンプルな関係式が導かれます。

B[i] = A[i] + A[i+1]

したがって、配列 A の各要素とその隣の要素を加算するだけで、隠れた配列 B を求めることができます。

for (i = 0; i < Aのサイズ; i++) {
    (A[i] + A[i+1]) を出力する
}

実装例

以下のC++コードで、実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
    for (int i = 0; i < A.size(); i++)
        cout << A[i] + A[i + 1] << ", ";
}
int main(){
    vector<int> A = { 6, -4, 8, -2, 3 };
    solve(A);
}

入力

{ 6, -4, 8, -2, 3 }

出力

2, 4, 6, 1, 3,

計算量

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n) と非常に効率的です。また、追加の配列を必要としないため、補助記憶領域も O(1) で済みます。隣接要素の和を取るというシンプルな発想で、交互符号の複雑な問題を線形時間で解決できる好例と言えるでしょう。