Quiz
- 1239A - Ivan the Fool and the Probability Theory
- https://codeforces.com/contest/1239/problem/A
- 縦横 n x mのタイルを”at most one adjacent cell of the same color”で塗る塗り方
AC Code
https://codeforces.com/contest/1248/submission/63080154
editorialの補足
- 白黒が交互に並んだ chess coloring 以外を考える
- 一番左の縦の列に、黒または白が2つ連続したものを考えると、それ以外の列は一意に決まる
- よって、一番左の縦の列の塗り方を考えればいい
- これはフィボナッチ数列になる
- editorialの2(Fn + Fm - 1)
- Fn : フィボナッチ
- -1 : ダブルカウントした chess coloring のボード
感想
- タイル塗りにフィボナッチが出てきて驚いた
- タイルの制約が2だからフィボナッチだけど、3ならトリボナッチだろう
