JOI qualifier 2014 D - Schedule of club activities

#algorithms

https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_d

NOTE
Sorry. This problem is in Japanese.

How to solve it?

dp[i][S] := The number of possible schedule for the case where the state of the club member is S on day i.
dp[i][S] = (total number of patterns meeting the previous day's conditions) % 10_007

Solution

use proconio::input;
pub fn main() {
    input!(
        n: usize,
        s: String,
    );
    let s = s.chars();
    let base = 10_007;
    // dp[date][universal set]
    let mut dp = vec![vec![0; 1 << 3]; n + 1];
    // Jが出席して、1日の場合のパターンは1つしかない
    dp[0][1] = 1;
    for (i, c) in s.enumerate() {
        let must = match c {
            'J' => 1,
            'O' => 1 << 1,
            'I' => 1 << 2,
            _ => panic!(),
        };
        for prev_j in 0..1 << 3 {
            for j in 0..1 << 3 {
                if must & j > 0 && prev_j & j > 0 {
                    dp[i + 1][j] += dp[i][prev_j];
                    dp[i + 1][j] %= base;
                }
            }
        }
    }
    println!("{}", dp[n].iter().sum::<usize>() % base);
}

if must & j > 0 && prev_j & j > 0 {
    dp[i + 1][j] += dp[i][prev_j];
    dp[i + 1][j] %= base;
}

The conditional statement of this expression is,

The representative is in the subset j,
The same person is a participant of the previous day (prev_j) and the same person on the day of the event to give the key. Counted only in the above cases.