[AOJ] No. 0595 部活のスケジュール表 (Schedule)

問題

方針

前日と今日のスケジュールの状態を考えれば良いので、動的計画法を行います。便宜上、与えられた文字列の先頭に 'J’ を挿入します。ここで、\( d(i, j) \) を \( i \) 日目の参加者の状態が \( j \) であるときに考えられるスケジュールの数とします。参加者の状態は、\( 2 \) 進数するものとします。\( 1 \) ビット目から順に J, O, I に対応させ、ビットが立っているときは参加しているものとします。

ここで、初期値を考えると、\( 0 \) 日目には J 君が参加していることから、ビット表記で表すと \( 001 \) となるので、\( d(0, 1) = 1 \) となります。次に、配列の遷移を考えます。前日の参加者の状態を \( j \), 今日の参加者の状態を \( k \) とすると、\( d(i, k) = d(i, k) + d(i – 1, j) \) となります。ただし、次の条件を満たす必要があります。

ここで、文字について、\( J = 001 \), \( O = 010 \), \( I = 100 \) とし、与えられた文字列の \( i \) 番目の文字をビットで表現した値を \( g_i \) とします。

  • 前日の責任者は、前日において参加している必要がある

この条件から、\( g_{i – 1} \wedge j \neq 0 \) を満たす必要があります。

  • 今日の責任者は、今日参加する必要がある

この条件から、\( g_{i} \wedge i \neq 0 \) を満たす必要があります。

  • 前日に参加した人の中で一人以上今日参加する必要がある

これは鍵を持って帰った人は次の日参加する必要があるという条件からくるもので、\( j \wedge k \neq 0 \) を満たす必要があります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    string s;
    cin >> s;
    ll mod = 10007;
    ll dp[N + 1][8]{};
    dp[0][1] = 1;
    map<char, int> m;
    m.insert(make_pair('J', 0));
    m.insert(make_pair('O', 1));
    m.insert(make_pair('I', 2));
    s.insert(0, "J");
    for (int i = 1; i <= N; i++) {
        int a = m[s[i - 1]];
        int b = m[s[i]];
        // j: 前日の参加者, k: 今日の参加者
        for (int j = 1; j < 8; j++) {
            for (int k = 1; k < 8; k++) {
                if (((1<<a) & j) == 0) continue;
                if (((1<<b) & k) == 0) continue;
                if ((j & k) == 0) continue;
                dp[i][k] += dp[i - 1][j];
                dp[i][k] %= mod;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 8; i++) {
        ans += dp[N][i];
    }
    ans %= mod;
    cout << ans << "\n";
    return 0;
}