ABC113-D:Number of Amidakuji

フィボナッチ数列が登場しがち。

解法

こういうのはdpが有効である。dp_{i,j}を位置iまででjに行くようなあみだくじの数とおく。dp_{i,j}の遷移先はdp_{i+1,j},dp_{i+1,j+1},dp_{i+1.j-1}のいずれかである。あとはそれぞれの遷移先について,そこに遷移するような位置(i+1)での横線の置き方の数がわかればよく,これはbit全探索することでO(2^W)でできる。本番でここが思いつかなかった。悲しいね。

ところで,次のような事実がある。

証明
Wに関する帰納法で示す。左から順に縦棒に1,2,\cdots W-2,W-1,Wと番号をつけることにしよう。W=0,1のときはそれぞれ1通りである。W-2,W-1での成立を仮定して,Wのときの横棒の置き方の数を求めよう。縦棒Wと縦棒W-1の間に横棒を置かないとき,横棒の置き方は1からW-1までの横棒の置き方に等しく,F_{W-1}通りある。縦棒Wと縦棒W-1の間に横棒を置くとき,横棒の置き方は1からW-2までの横棒の置き方に等しく(縦棒W-1と縦棒W-2の間には横棒が置けないから),F_{W-2}通りある。よって,Wのときの横棒の置き方の数はF_{W-1}+F_{W-2}=F_W通りである。

すると,bit全探索などする必要がないことがわかる。例えば,dp_{i,j}からdp_{i+1,j-1}への遷移を考えよう。このような遷移が起きる条件は

  1. jj-1の間に横棒がある
  2. j-1j-2の間に横棒がない
  3. jj-1の間に横棒がない

の3つである。これらの条件を満たすような位置i+1での横棒の置き方は,「縦棒1から縦棒j-2までの横棒の置き方」と「縦棒jから縦棒Wまでの横棒の置き方」の積であるから,F_{j-2}\times F_{W-j}通りある。つまり,遷移がO(1)で可能であることがわかる。他の遷移も同様にしてできる(コード参照)。天才だ。

提出

Submission #3543308 - AtCoder Beginner Contest 113

フィボナッチ数列が現れるのは面白いが,bit全探索で解けなかったのは情けなかった。