ABC215E - Chain Contestant

考え方

DPで前から決めていけば良いことはわかる．

DPを更新するためには，

• 前から何番目まで決めたか
• すでに使った文字の集合
• 最後に選んだ文字の種類

がわかれば良い（dp[i][j][k]で表す）．使った文字の集合はbitで管理できる．

【更新ルール】
$i$番目まで決めたとき，$i + 1$番目まで考えると「$i + 1$番目を選ばない」方法がdp[i][j][k]通り存在する．

さらに，

• $i + 1$番目の文字が未使用であるか
• $i + 1$番目の文字が前ステップの最後の文字と一致しているか

を満たす場合には，「$i + 1$番目の文字を選ぶ」方法がdp[i][j][k]通り存在する．

回答例

各$i + 1$に対し，$i + 1$回目で初めて参加した場合を1として（ループの中で）初期化する．

N = int(input())
S = list(input())
S = [ord(s) - ord('A') for s in S]
mod = 998244353

dp = [[[0] * 10 for _ in range(1 << 10)] for _ in range(N + 1)]

for i in range(N):
    dp[i + 1][1 << S[i]][S[i]] = 1
    for j in range(1 << 10):
        for k in range(10):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j][k] %= mod
            if (j >> S[i] & 1) and k != S[i]:
                continue
            dp[i + 1][j | 1 << S[i]][S[i]] += dp[i][j][k]
            dp[i + 1][j | 1 << S[i]][S[i]] %= mod

ans = 0
for j in range(1, 1 << 10):
    for k in range(10):
        ans += dp[N][j][k]
        ans %= mod
print(ans)

【初期化方法を工夫する】

• 答えは，一つも選ばない場合を除く必要があるので，空集合（$j=0$）は初期化のために好きに使ってよい．
• 空集合（$j=0$）からの遷移が全て$1$になってほしい

を満たすように初期化すると，DPの更新ルールから，任意の$k$を一つ選んで
dp[0][0][k] = 1とすれば良い．

N = int(input())
S = list(input())
S = [ord(s) - ord('A') for s in S]
mod = 998244353

dp = [[[0] * 10 for _ in range(1 << 10)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(1 << 10):
        for k in range(10):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j][k] %= mod
            if (j >> S[i] & 1) and k != S[i]:
                continue
            dp[i + 1][j | 1 << S[i]][S[i]] += dp[i][j][k]
            dp[i + 1][j | 1 << S[i]][S[i]] %= mod

ans = 0
for j in range(1, 1 << 10):
    for k in range(10):
        ans += dp[N][j][k]
        ans %= mod
print(ans)