Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 291 D問題 Flip Cards

AtCoder ABC291 ABC 400 pts D問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 枚のカードが一列に並んでいる. 左から $i$ 番目のカードの表には整数 $A_i$ が, 裏には整数 $B_i$ が書かれている.

各カードを表か裏が上になるようにカードを置く. このようなカードの置き方のうち, 隣り合っているカードに書かれている整数が等しい箇所がないような置き方の数を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq 10^9$

解法

左から順に表裏を決めることにすると, $i$ 番目のカードの表裏の可否は $(i-1)$ 番目のカードの状態のみから決定される. このことから, 動的計画法で求めることが有用になる.

$i=1,2, \dots, N$ と $X \in \{H,T\}$ に対して, ${\rm DP}[i,X]$ を以下で定める.

左から $i$ 番目のカードを条件を満たしながら決定した時, $i$ 番目のカードが $X=H$ ならば表, $X=T$ ならば裏であるような置き方の方法の数.

このとき, 最終解答は ${\rm DP}[N,H]+{\rm DP}[N,T]$ である.

ベースケースについては $i=1$ のときで, ${\rm DP}[1,H]={\rm DP}[1,T]=1$ である.

更新式について, ${\rm DP}[i, H]$ について, $(i-1)$ 枚目のカードの整数について場合分けすると,

${\rm DP}[i,H]=\begin{cases} {\rm DP}[i-1, H] & (A_{i-1} \neq A_i) \\ 0 & (A_{i-1}=A_i) \end{cases}+\begin{cases} {\rm DP}[i-1, T] & (B_{i-1} \neq A_i) \\ 0 & (B_{i-1}=A_i) \end{cases}$

となる. ${\rm DP}[i, T]$ についても同様である.

よって, 要素数 $2N$ , 更新の計算量が $O(1)$ 時間/要素であるので, 時間計算量 $O(N)$ 時間で解くことができた.