ThreeSameLetters [2018 TCO Algorithm Round 1B Hard]

以下を満たす文字列は何通りあるか。

• 長さL
• アルファベットの最初のS個だけを使う
• 連続する長さ3の文字列で全て同じ文字である文字列がただ1つだけある

解法

DPで解く。
dp[i][j][len][ok] := 文字列がi文字分確定していて、最後の文字がjで、最後の文字がlen文字分連続していて、今までに連続する長さ3の文字列で全て同じ文字である文字列があるか(ok=0:ない、ok=1:ある)の場合の数
これを更新していって、答える。

mint dp[30][30][4][2];
struct ThreeSameLetters {
    int countStrings(int L, int S) {
        dp[0][29][0][0] = 1;
        rep(i, 0, L) rep(j, 0, 30) rep(len, 0, 4) rep(ok, 0, 2) {
            rep(nxt, 0, S) {
                if (j != nxt) dp[i + 1][nxt][1][ok] += dp[i][j][len][ok];
                else {
                    if (len < 2) dp[i + 1][j][len + 1][ok] += dp[i][j][len][ok];
                    else {
                        if (ok == 0) dp[i + 1][j][3][1] += dp[i][j][len][ok];
                    }
                }
            }
        }

        mint ans = 0;
        rep(j, 0, 30) rep(len, 0, 4) ans += dp[L][j][len][1];
        return ans.get();
    }
};