Magicode logo
Magicode
・2 min read

ABC291 D-Flip Cards

競技プログラミングAtCoderPython
https://cdn.magicode.io/media/notebox/blob_5i7Q8w9

問題文

表裏に数字が書かれたカードがN枚あり、隣接するカードの数字が異なるように裏返したりしなかったりしたときの組合せを998244353で割ったあまりを求める。

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤Ai,Bi≤1091 \le A_i, B_i \le 10^9

解説

問題文の通り、すべてのカードの裏表の組合せを列挙する場合は2N2^Nだけあり、今回の制約では2secで計算することができない。
今回の場合、各カードの裏表を出力する必要はないため、ii番目のカードを表とした時と裏にした時の組合せの数だけがわかれば良い。 また、ii番目のカードの値を決める時には両隣の数値と異なる必要があるが、既に値が決まっているi−1i-1番目のカードだけ見れば、ii番目のカードの表裏を決めることができる。
したがって、各カードを表にした時と裏にした時のそこまでで決まっているカードの組合せの数を足すことで、組合せの数をDPによって計算することができる。
DP[i][0]DP[i][0]をii番目を表にした時のそこまでの組合せの数、DP[i][1]DP[i][1]を裏にした時の組合せの数として、NN番目のカードを表、裏にした時の組合せの和のあまりを出力することで、O(N)O(N)答えを求めることができる。

解答例

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]
mod = 998244353
dp = [[0, 0] for _ in range(N + 1)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(1, N):
    # 1つ前の表-表
    if A[i - 1] != A[i]:
        dp[i][0] += dp[i - 1][0]
    # 1つ前の表-裏
    if A[i - 1] != B[i]:
        dp[i][1] += dp[i - 1][0]
    # 1つ前の裏-表
    if B[i - 1] != A[i]:
        dp[i][0] += dp[i - 1][1]
    # 1つ前の裏-裏
    if B[i - 1] != B[i]:
        dp[i][1] += dp[i - 1][1]
    # 途中で値が大きくなりすぎないようにあまりを計算しておく
    dp[i][0] %= mod
    dp[i][1] %= mod
print(sum(dp[N - 1]) % mod)

Discussion

コメントにはログインが必要です。