ABC113-D:Number of Amidakuji
フィボナッチ数列が登場しがち。
解法
こういうのはdpが有効である。を位置まででに行くようなあみだくじの数とおく。の遷移先はのいずれかである。あとはそれぞれの遷移先について,そこに遷移するような位置での横線の置き方の数がわかればよく,これはbit全探索することででできる。本番でここが思いつかなかった。悲しいね。
ところで,次のような事実がある。
証明
に関する帰納法で示す。左から順に縦棒にと番号をつけることにしよう。のときはそれぞれ通りである。での成立を仮定して,のときの横棒の置き方の数を求めよう。縦棒と縦棒の間に横棒を置かないとき,横棒の置き方はからまでの横棒の置き方に等しく,通りある。縦棒と縦棒の間に横棒を置くとき,横棒の置き方はからまでの横棒の置き方に等しく(縦棒と縦棒の間には横棒が置けないから),通りある。よって,のときの横棒の置き方の数は通りである。
すると,bit全探索などする必要がないことがわかる。例えば,からへの遷移を考えよう。このような遷移が起きる条件は
- との間に横棒がある
- との間に横棒がない
- との間に横棒がない
の3つである。これらの条件を満たすような位置での横棒の置き方は,「縦棒から縦棒までの横棒の置き方」と「縦棒から縦棒までの横棒の置き方」の積であるから,通りある。つまり,遷移がで可能であることがわかる。他の遷移も同様にしてできる(コード参照)。天才だ。