xxxasdfghjk999のブログ

iroiro

yukicoder No.314 ケンケンパ

問題

No.314 ケンケンパ - yukicoder

解法

ケンケンパの生成について, 3つの状態があります.

パで終わっている
末尾にケンが1回連続で出現して終わっている
末尾にケンが2回連続で出現して終わっている

遷移しうる状態は
1 → 2
2 → 1 , 3
3 → 1
よりDPを組み立てると, (0-indexedで組みます)
$dp[i][j] = (長さiまでの生成パターンについて, パターンjに含まれるもの)$
として, 右辺を固定して配るdpをすると,

初期値

$dp[0][0] = 1$

$j = 0 のとき$

$dp[i+1][j+1] += dp[i][j]$

$j = 1 のとき$

$dp[i+1][j+1] += dp[i][j] \\ dp[i+1][j-1] += dp[i][j]$

$j = 2 のとき$

$dp[i+1][j-2] += dp[i][j]$
これを $0 \leq i < N , \space 0 \leq j \leq 2$ について回すと,
$\sum_{j=0}^{2} dp[N][j]$ が答えです.

提出

#279160 No.314 ケンケンパ - yukicoder

感想

前後のみを見るdpなので, 領域を節約できないかとi%2 でインデックスしたもので実装してもみたものの, なんでかバグって正しい答えが出力されませんでした... どうしてでしょう.