問題概要

J 君と、O 君と、I 君の 3 人が所属する部活動がある。 $N$ 日間の活動が行われる。それぞれの日において責任者が誰なのかがあらかじめ決まっている。このとき、以下の条件を満たす必要がある (責任者への鍵の受け渡しの都合)。

その日の責任者はかならず出席しなければならない
初日は J 君がかならず出席しなければならない (J 君が最初に鍵を持っているため)
どの連続する 2 日間も、同一人物が出席しなければならない
- その同一人物はかならずしも、その 2 日間の責任者である必要はない (その人が鍵を自宅に持って帰ればよいため)

$N$ 日間の活動においてそれぞれに日程に誰が出席しているかを表す状況は $8^{N}$ 通り考えられるが、そのうち上記の条件を満たすものが何通りあるか、10007 で割ったあまりを求めよ。

制約

$2 \le N \le 1000$

考えたこと

平たく言えばこういう問題と言える。

$3 \times N$ のグリッドがあって、各列にはちょうど 1 個のマスが黒く塗られている (残りはすべて白色)

残りの白色マスのうちのいくつかを黒く塗りたい。次の条件を満たすものが何通りあるか求めよ。

左上のマスは黒く塗る (すでに塗られているならば気にしない)
どの連続する 2 列についても、ある行が存在して、その行はともに黒く塗られている (1 × 2 の長方形によって各列を繋ぐイメージ)

このような「幅が短くて、長さがめっちゃ長い」という長方形形状の色塗り問題は、bit DP をまずは疑う。つまり、

dp[ i ][ bit ] := 最初の i 列を白黒に塗り分ける方法のうち、最後の列の黒マスの箇所が bit で表されるようなものが何通りあるか

とする。そして、

bit → bit2 の遷移が OK のとき
dp[ i + 1 ][ bit2 ] += dp[ i ][ bit ]

と更新すれば解ける！　計算量は $O(N)$ 。

コード

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

const int MOD = 10007;
int main() {
    int N;
    string S;
    cin >> N >> S;

    auto add = [&](long long &a, long long b) -> void {
        a += b;
        if (a >= MOD) a -= MOD;
    };
    vector<vector<long long>> dp(N+1, vector<long long>(8, 0));
    dp[0][1] = 1;
    for (int i = 0; i < N; ++i) {
        int sekinin;
        if (S[i] == 'J') sekinin = 0;
        else if (S[i] == 'O') sekinin = 1;
        else sekinin = 2;
        for (int bit = 0; bit < (1<<3); ++bit) {
            for (int bit2 = 0; bit2 < (1<<3); ++bit2) {
                if (!(bit2 & (1<<sekinin))) continue;
                if (!(bit & bit2)) continue;
                add(dp[i+1][bit2], dp[i][bit]);
            }
        }
    }
    long long res = 0;
    for (int bit = 0; bit < (1<<3); ++bit) add(res, dp[N][bit]);
    cout << res << endl;       
}