ABC291 D問題 Flip Cards

atcoder.jp

動的計画法で1枚目から順に数えていく

枚目のカードまで条件を満たしていたとき、 枚目のカードを加えたときに
条件を満たしたままかどうかは、枚目と 枚目のカードの表/裏の向きだけに依存します。
そこで、動的計画法のdp[flag][i] は、枚目のカードまで条件を満たしている選び方のうち、枚目のカードの向きが 表(flag = 1) または裏(flag = 2) の数、と定義します。

カードに書かれた数が全部異なる場合、
dp[1][i] = dp[1][i-1] + dp[2][i-1]
dp[2][i] = dp[1][i-1] + dp[2][i-1]
のように計算できます。カードに書かれた数が同じになる組み合わせがあれば、その項を除いて計算します。

コード例 (Julia)

function solve()

  MOD_ = 998244353

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  A = zeros(Int,N)
  B = zeros(Int,N)
  dp = zeros(Int,2,N)

  for i = 1:N
    A[i],B[i] = readInts()
  end

  dp[1,1] = dp[2,1] = 1

  for i = 2:N
    if A[i-1] != A[i]
      dp[1,i] += dp[1,i-1]
    end
    if A[i-1] != B[i]
      dp[2,i] += dp[1,i-1]
    end
    if B[i-1] != A[i]
      dp[1,i] += dp[2,i-1]
    end
    if B[i-1] != B[i]
      dp[2,i] += dp[2,i-1]
    end

    dp[1,i] %= MOD_
    dp[2,i] %= MOD_
  end

  println( (dp[1,N]+dp[2,N])%MOD_ )

end  # function solve

# main
solve()