C++で各ステーションの最終的な放射強度を計算する方法

直線上にN個のステーションが並んでおり、それぞれが非負の放射出力を持っていると仮定します。各ステーションは、一定のルールに従って隣接するステーションの放射強度を高めます。

例えば、ステーションiの放射強度がRであるとき、このステーションは左側では(i-1)番目のステーションの放射強度を「R-1」だけ、(i-2)番目のステーションを「R-2」だけ増やします。同様に右側でも、(i+1)番目のステーションに「R-1」、(i+2)番目のステーションに「R-2」を加えます。距離が1つ離れるごとに寄与は1ずつ減少し、その値が0以下になった時点で影響は及ばないものとします。

具体例

配列 Arr = [1, 2, 3] の場合を考えてみましょう。

• ステーション0（強度1）: 隣のステーション1への寄与は R-1 = 0 となるため影響なし
• ステーション1（強度2）: ステーション0とステーション2にそれぞれ +1
• ステーション2（強度3）: ステーション1に +2、ステーション0に +1

したがって、最終的な放射強度は次のように計算されます。

[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> findFinalRadiation(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, 0);

    for (int i = 0; i < n; i++) {
        result[i] += arr[i];

        // 左方向への伝播
        int power = arr[i] - 1;
        for (int j = i - 1; j >= 0 && power > 0; j--) {
            result[j] += power;
            power--;
        }

        // 右方向への伝播
        power = arr[i] - 1;
        for (int j = i + 1; j < n && power > 0; j++) {
            result[j] += power;
            power--;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3};
    vector<int> result = findFinalRadiation(arr);

    cout << "最終的な放射強度 : ";
    for (int r : result)
        cout << r << " ";
    return 0;
}

出力

最終的な放射強度 : 3 4 4

計算量

時間計算量はO(N²)、空間計算量はO(N)となります。ステーション数Nが大きくなるほど処理に時間がかかるため、累積和や差分の考え方を取り入れることで、より効率的に高速化することも可能です。