K日後のアクティブ・非アクティブセルを求めるアルゴリズムとC++実装

問題概要

今回は興味深い問題を取り上げます。サイズn（n > 3）のバイナリ配列が与えられているとします。値が1（true）は「アクティブ」状態を、0（false）は「非アクティブ」状態を表します。さらに、日数を表す整数kも与えられ、k日後における各セルの状態を求めることが目的です。

毎日の更新ルールは次のとおりです。i番目のセルは、その左隣と右隣のセルの状態が異なる場合にアクティブ（1）となり、同じ場合には非アクティブ（0）となります。なお、最も左端と右端のセルには外側に隣接するセルが存在しないため、これらは常に0として扱われます。

具体例

例を使って動作を確認してみましょう。配列が {0, 1, 0, 1, 0, 1, 0, 1} で、k = 3 の場合、日ごとの変化は以下のようになります。

• 1日後：{1, 0, 0, 0, 0, 0, 0, 0}
• 2日後：{0, 1, 0, 0, 0, 0, 0, 0}
• 3日後：{1, 0, 1, 0, 0, 0, 0, 0}

したがって、3日後の時点でアクティブセルが2個、非アクティブセルが6個ということになります。

アルゴリズム

activeCellKdays(arr, n, k)

begin
    make a copy of arr into temp
    for i in range 1 to k, do
        temp[0] := 0 XOR arr[1]
        temp[n-1] := 0 XOR arr[n-2]
        for each cell i from 1 to n-2, do
            temp[i] := arr[i-1] XOR arr[i+1]
        done
        copy temp to arr for next iteration
    done
    count number of 1s as active, and number of 0s as inactive, then return the values.
end

手順を日本語で整理すると、次のようになります。

1. 元の配列arrを一時配列tempにコピーします。
2. k回の反復処理を行います。各反復では、両端のセルを temp[0] = 0 XOR arr[1]、temp[n-1] = 0 XOR arr[n-2] として計算します。
3. 中間の各セルについては、左右の隣接セルのXORを取って temp[i] = arr[i-1] XOR arr[i+1] とします。
4. 次の反復に備えて、tempの内容をarrへ書き戻します。
5. すべての反復が終わった後、1の個数をアクティブ、0の個数を非アクティブとして数え、結果を出力します。

このアルゴリズムの時間計算量はO(k × n)、必要な追加メモリはO(n)です。

C++による実装例

#include <iostream>
using namespace std;
void activeCellKdays(bool arr[], int n, int k) {
    bool temp[n]; // tempはarrのコピーを保持する
    for (int i=0; i<n ; i++)
        temp[i] = arr[i];
    for(int i = 0; i<k; i++){
        temp[0] = 0^arr[1]; // 左端のセルの値を設定
        temp[n-1] = 0^arr[n-2]; // 右端のセルの値を設定
        // 中間の全セルについて、左右が異なれば1を設定
        for (int i=1; i<=n-2; i++)
        temp[i] = arr[i-1] ^ arr[i+1];
        // 次の反復のためにtempをarrへ書き戻す
        for (int i=0; i<n; i++)
            arr[i] = temp[i];
    }
    int active = 0, inactive = 0;
    for (int i=0; i<n; i++)
        if (arr[i])
            active++;
        else
            inactive++;
    cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive;
}
main() {
    bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    activeCellKdays(arr, n, k);
}

実行結果

Active Cells = 2, Inactive Cells = 6