C++で各放射局の最終的な放射強度を求める方法

直線上にN個の局(ステーション)が並んでおり、それぞれが同じ非負の放射パワーを持っているとします。各局は、自分の放射パワーに応じて、隣接する局の放射パワーを次のルールで増加させます。

例えば、局iの放射パワーがRである場合、(i−1)番目の局の放射パワーを「R−1」だけ、(i−2)番目の局の放射パワーを「R−2」だけ増加させます。同様に、(i+1)番目の局の放射パワーを「R−1」だけ、(i+2)番目の局の放射パワーを「R−2」だけ増加させ、これを繰り返します。つまり、局から離れるほど影響が1ずつ減っていく仕組みです。

計算例

配列が Arr = [1, 2, 3] の場合、出力は 3, 4, 4 になります。新しい放射パワーは次のように計算されます。

[1 + (2 − 1) + (3 − 2), 2 + (1 − 1) + (3 − 1), 3 + (2 − 1)] = [3, 4, 4]

アルゴリズムの考え方

考え方はシンプルです。各局iについて、距離に応じて減衰した実効放射パワーが負になるまで、隣接する局の放射パワーを順に加算していきます。これをすべての局に対して行うことで、各局の最終的な放射パワーを求めることができます。

C++での実装例

#include <iostream>
#include <vector>
using namespace std;

vector<int> finalRadiation(vector<int>& arr, int n) {
    vector<int> result(n, 0);
    for (int i = 0; i < n; i++) {
        // 自分自身の放射パワーを加算
        result[i] += arr[i];
        // 左方向への影響
        for (int j = i - 1, k = 1; j >= 0 && arr[i] - k > 0; j--, k++) {
            result[j] += arr[i] - k;
        }
        // 右方向への影響
        for (int j = i + 1, k = 1; j < n && arr[i] - k > 0; j++, k++) {
            result[j] += arr[i] - k;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3};
    int n = arr.size();
    vector<int> result = finalRadiation(arr, n);
    for (int x : result) {
        cout << x << " ";
    }
    return 0;
}

出力

3 4 4

計算量について

この実装では、各局ごとに左右両方向の影響を調べるため、時間計算量はO(N²)となります。Nが非常に大きい場合は、差分配列や累積和のテクニックを組み合わせることで、O(N)程度まで高速化することも可能です。