[AOJ] No. 0568 パスタ (Pasta)

2019年11月23日

問題

方針

\( 3 \) 日以上同じパスタを選んではいけないという制約がポイントです。\( i + 1 \) 日目の予定を決めるためには、\( i \) 日目と \( i – 1 \) 日目の予定が影響することを考えて動的計画法を行います。ここで、\( d(i, j, k) \) を \( i \) 日目にパスタ \( j \) を選び、\( i + 1 \) 日目にパスタ \( k \) を選ぶ時の場合の数とします。また、\( d \) は \( 0 \) で初期化します。

ここで、\( i \) 日目のパスタの予定を \( c_i \) とします。予定がないときは \( c_i = -1 \) とします。

初期値

\( c_1 = -1 \wedge c_2 = -1\) のとき

このとき、\( d(1, i, j) = 1  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3)\) となります。これは、\( 1 \) 日目と \( 2 \) 日目に予定が入っていないことになります。

\( c_1 \neq -1 \wedge c_2 \neq -1\) のとき

このとき、\( d(1, c_1, c_2) = 1 \) となります。

\( c_1 = -1 \wedge c_2 \neq -1\) のとき

このとき、\( d(1, i, c_2) = 1 (1 \leq i \leq 3)\) となります。

\( c_1 \neq -1 \wedge c_2 = -1\) のとき

このとき、\( d(1, c_1, i) = 1 (1 \leq i \leq 3)\) となります。

更新式

\( c_i = -1 \wedge c_{i+1} = -1\) のとき

このとき、\( d(i, j, k) \gets d(i, j, k) + d(i – 1, l, j) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge 1 \leq l \leq 3 \wedge j \neq k \wedge k \neq l)\) となります。右辺の \( d(i, j, k)\) と \( d(i – 1, l, j) \) において、\( j \) が共通しているのは、\( i \) 日目の \( j \) を選択するという遷移は、\( i -1 \) 日目において、次の日に \( j \) を選択していなければならないからです。

\( c_i \neq -1 \wedge c_{i+1} \neq -1\) のとき

このとき、\( d(i, c_i, c_{i+1}) \gets d(i, c_i, c_{i+1}) + d(i – 1, j, c_i) \  (1 \leq j \leq 3 \wedge c_i \neq c_{i+1} \wedge j \neq c_i)\) となります。

\( c_i = -1 \wedge c_{i+1} \neq -1\) のとき

このとき、\( d(i, j, c_{i+1}) \gets d(i, j, c_{i+1}) + d(i – 1, k, j) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge j \neq c_{i+1} \wedge j \neq k)\) となります。

\( c_i \neq -1 \wedge c_{i+1} = -1\) のとき

このとき、\( d(i, c_i, j) \gets d(i, c_i, j) + d(i – 1, k, c_i) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge j \neq c_{i} \wedge j \neq k)\) となります。

コード

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

ll dp[101][3][3]{};
ll mod = 10000;

void init(int a, int b) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a == -1 && b == -1) {
                dp[1][i][j] = 1;
            } else if (a != -1 && b != -1) {
                dp[1][a][b] = 1;
                return;
            } else if (a == -1 && b != -1) {
                dp[1][i][b] = 1;
            } else if (a != -1 && b == -1) {
                dp[1][a][j] = 1;
            }
        }
    }
}

// d日目にa, d+1日目にb
void solve(int d, int a, int b) {
    if (a == -1 && b == -1) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (i == j && i == k) continue;
                    dp[d][i][j] += dp[d - 1][k][i];
                    dp[d][i][j] %= mod;
                }
            }
        }
    } else if (a != -1 && b != -1) {
        for (int i = 0; i < 3; i++) {
            if (i == a && a == b) continue;
            dp[d][a][b] += dp[d - 1][i][a];
            dp[d][a][b] %= mod;
        }
    } else if (a == -1 && b != -1) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (b == i && i == j) continue;
                dp[d][i][b] += dp[d - 1][j][i];
                dp[d][i][b] %= mod;
            }
        }
    } else if (a != -1 && b == -1) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (a == i && i == j) continue;
                dp[d][a][i] += dp[d - 1][j][a];
                dp[d][a][i] %= mod;
            }
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    int A[N], B[N];
    int C[N + 1];
    fill(C, C + N + 1, -1);
    for (int i = 0; i < K; i++) {
        cin >> A[i] >> B[i];
        B[i]--;
        C[A[i]] = B[i];
    }
    
    // dp[i][j][k] i日目にj、i+1日目にkの個数
    init(C[1], C[2]);
    for (int i = 2; i < N; i++) {
        solve(i, C[i], C[i + 1]);
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ans += dp[N - 1][i][j];
        }
    }
    cout << ans % mod << "\n";
    return 0;
}