マシュマロ（Kyuride Kagamiz Programming Contest [D])

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

個人的には、読解難でした。

読解パート

「地点」は、往路・復路で同じ地点を指しています。ただし、水たまりの有無は往路・復路で違うようです。ここが分かれば、読み解けると思います。

解法

地点 $0, 1, 2, \ldots$ 順に、次を計算します。

• 地点 $n$ までの往路・復路の置き方を決める決め方のうちで、地点 $n$ について次のそれぞれが成り立つ方法の数え上げ。
  • 往路にも復路にも置く場合
  • 往路には置いて、復路には置かない場合
  • 往路には置かず、復路には置く場合

これを、$2$ 地点連続で「置かない」という選択肢をとらないように計算していきます。 $O(K+R)$ 時間で解くことができます。