JOI難易度６ 部活のスケジュール表

問題原文

atcoder.jp

問題要旨

J君とO君とI君がいるような部活動の、 日間のスケジュールを考える。
部室のドアを開けるためには、鍵が必要であり、鍵はその前日に部活に参加した人のうちの１人が持って帰ることができる。（最初、鍵はJ君が持っている） 部室のドアが開けられないと活動は始められない（プログラミング部なので）
また、各活動日には「責任者」が１人割り振られており、必ず部活に参加しなければならない。
全ての活動日に部活動を行うことができるような組み合わせの通り数を、10007で割ったあまりを求めよ。

• 

解法

日目に という人の組み合わせで部活に参加する通り数 として、dpテーブルを埋めていく。

J君 → 1, O君→2, I君 → 4 というふうに　エンコードすれば、例えばO君とI君という組み合わせは、 011 と表すことができる。
あとは、「責任者を含まないような組み合わせ」と「前の日に部活に参加した人が一人もいないような人の組み合わせ（鍵を持っている人がこないパターン）」を省きながら数え上げればよい。

実装

N = int(input())
S = list(input())
MOD = 10007

X = []
for s in S:
    if s == 'J':
        X.append(1)
    elif s == 'O':
        X.append(2)
    else:
        X.append(4)


# dp[i][bs] := i日目にbsという人の組み合わせを使う時の通り数
dp = [[0] * 9 for _ in range(N + 1)]
dp[0][1] = 1

for i, x in enumerate(X, start=1):
    for bs in range(1, 9):
        if not (x & bs):
            continue
        for pre_bs in range(1, 9):
            if bs & pre_bs:
                dp[i][bs] += dp[i - 1][pre_bs]
                dp[i][bs] %= MOD

print(sum(dp[-1]) % MOD)

感想

これが自明に見えたのは結構嬉しい。
JOIはDP力が鍛えられていいなぁ。。。