ARC071-F Infinite Sequence

問題リンク

解法

前からDPしていく.

2以上の要素が2連続するとそこから先はすべて埋まり、そうでない場合1を置くか、2以上の要素を置いた後十分になるまで1で埋めるしかない。 これを考えると、 を、「 要素目以降がまだ決定していない場合の数」としてDPができる。

遷移を Segment Tree で高速化すれば、 が達成できる。

感想

数え上げDP、バグりがちなので鍛えたい