C++で解く「N日後の監獄の独房」問題：14日周期を利用した効率的な解法

問題の概要

8つの独房が一列に並んでおり、各部屋には囚人が収容されているか、空室であるかのどちらかだとします。毎日、各部屋の占有状態は以下のルールに従って変化します。

• ある部屋の両隣が、どちらも占有されている（またはどちらも空室である）場合 → その部屋は翌日占有状態になります。
• それ以外の場合 → その部屋は翌日空室になります。

監獄の現在の状態は配列で表現します。i番目の部屋が占有されていれば cells[i] は 1、空室なら 0 となります。監獄の初期状態と日数 N が与えられたとき、N日後の監獄の状態を求めるのがこの問題の目的です。

具体例

入力が [0,1,0,1,1,0,0,1]、N = 7 の場合、出力は [0,0,1,1,0,0,0,0] になります。7日間の状態遷移は以下の通りです。

Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

解法のポイント：14日周期のサイクル

この問題を単純に解くなら、状態遷移をN回シミュレーションすることになりますが、Nが非常に大きい場合は非効率です。ここで鍵となるのが周期性です。

初日以降、両端の部屋は必ず空室（0）になります。両端の部屋には隣接する部屋が1つしかなく、「両隣の状態が一致する」という条件を満たせないためです。したがって、実際に状態が変化しうるのは中間の6部屋だけで、状態の総数は最大でも 2⁶ = 64 通りです。さらに、到達可能な状態は限られており、状態は14日周期で同じパターンを繰り返すことが知られています。

この性質を利用すれば、最初の14日分の状態を事前に記録しておき、あとは N mod 14 に対応する状態を参照するだけで答えが求まります。

アルゴリズムの手順

1. 日ごとの状態を格納するマップ m と、訪問済み状態を記録するセット visited を作成します。
2. N が 0 の場合は、初期状態 cells をそのまま返します。
3. 初期状態を visited に挿入します。
4. i を 1 から 14 まで繰り返します。
   • サイズ8の配列 temp を作成します。
   • j を 1 から 6 について、cells[j-1] と cells[j+1] のXORが 0（＝両隣の状態が一致）であれば temp[j] = 1、それ以外は 0 とします。
   • cells を temp で更新し、m[i] に記録して visited に挿入します。
5. N が 14 で割り切れる場合は m[14] を、それ以外の場合は m[N % 14] を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
    public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        map<int, vector<int>> m;
        if(N == 0) return cells;
        set<vector<int>> visited;
        visited.insert(cells);
        for(int i = 1; i <= 14; i++){
            vector<int> temp(8);
            for(int j = 1; j < 7; j++){
                // 両隣の状態が一致していれば占有(1)
                if((cells[j - 1] ^ cells[j + 1]) == 0){
                    temp[j] = 1;
                }
            }
            cells = temp;
            m[i] = temp;
            visited.insert(temp);
        }
        return m[N % 14 == 0 ? 14 : N % 14];
    }
};

int main(){
    vector<int> v1 = {0,1,0,1,1,0,0,1};
    Solution ob;
    print_vector(ob.prisonAfterNDays(v1, 7));
}

入力

[0,1,0,1,1,0,0,1]
7

出力

[0,0,1,1,0,0,0,0]

まとめ

この問題の核心は、状態遷移が14日周期で循環することを見抜けるかにあります。すべての日を愚直にシミュレートする代わりに、最初の14日分の状態を事前計算しておけば、Nがどれほど大きくても定数時間で答えを導き出せます。また、「両端の部屋は初日以降必ず空室になる」という観察が、探索すべき状態空間を絞り込む重要なヒントとなります。