はまやんはまやんはまやん

hamayanhamayan's blog

FourLamps [TopCoderOpen 2017 Round2A Div1 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=14597&rd=16929

問題概要

N個のランプがあり、on/offのどちらかの状態をとる。
最初はinitの状態になっている。
ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通りか。

1. 連続する4つのランプを選ぶが、少なくとも1つがonか少なくとも1つがoffで無ければならない
2. この4つのランプの中心を分割点として、N個のランプ全体を前半・後半の2つに分ける
3. 前半・後半のどちらかを選ぶ
4. 選んだ方を反転させる






















解説

プロの解法を見るとDPで解いている。
プロからのヒント