ABC113 D - Number of Amidakuji - ツバサの備忘録

問題
 提出コード
DPをします。
まずは、下準備をします。
ある高さについて、幅が $x$ のとき(つまり、 $x+1$ 本の棒があるとき)に、横線の置き方がいくつあるかを計算します。
これを $memo[x]$ とします。 $x=0$ のとき、横線はおけないので $memo[0]=0$ です。
$x=1$ のとき、横線を置くか置かないかの2通りです。よって $memo[1]=2$ です。
$x=2$ のときについて考えます。
横線を置くと1、置かないと0とすると、
00,01,10の3通りです。
$memo[2]=3$ です。
これ以降については、実はフィボナッチ数列のようになっています。
幅が $x$ のとき、一番右側に横線を置くか置かないかで場合分けをします。

横線を置かないとき
一番右端を除く、 $x-1$ の幅についての置き方を考えればよいので、これは
$memo[x-1]$ になります。
横線を置くとき
一番右端に横線を置くと、その左側は自動的に横線を置くことができなくなります。
残った $x-2$ の幅については自由に置くことができるので、これは
$memo[x-2]$ になります。

ということで、
$memo[x] = memo[x-1]+memo[x-2]$
となります。
$W$ の最大値が8なので、これは手計算で求めてもいいですし、プログラムを書いて $O(W)$ で求めてもいいと思います。

さて、答えの数え上げをしていきます。
$dp[i][j]=$ 一番上の高さのときに、一番左の棒からスタートしたときに、上から $i$ 番目の高さにいるときに、左から $j$ 番目にたどり着くようなものの個数
とします( $j$ は0-indexedとします)。初期状態は、 $dp[0][0]=1$ です。
すると、
$i-1$ のときに、 $j-1$ 、 $j$ 、 $j+1$ の3つのどこかにいる必要があります。
それぞれ、 $i-1$ のときに、左上、真上、右上にいて、そこから横線を通り（または通らず）、今の場所に移動します。

左(右)上から移動してくる場合
考えることは同じなので、今回は左上から移動する場合についてのみ考えます。
$j$ 番目の棒線にたどり着くとき、 $j-1$ と $j$ の区間に横線を引くため、 $j$ と $j+1$ および $j-2$ と $j-1$ の区間には、横線があってはいけません。
ですが、それ以外の部分は自由に横線をひくことができます。
この部分は、 $j$ より左側と右側に分割することができ、幅がそれぞれ
$w-1-(j+1)$ と $j-2$ になります。
ということで、この二つの幅についての横線の置き方は、 $memo$ を参照することで求められます。
あとは、その二つと $dp[i-1][j-1]$ を掛け算すればよいので、
$memo[w-1-(j+1)]×memo[j-2]×dp[i-1][j-1]$
となります。
同様にすると、右上から移動するパターンは
$memo[w-1-(j+2)]×memo[j-1]×dp[i-1][j+1]$
となります。
移動せずに降りてくる場合
$j$ の左右には横線があってはいけません。しかし、それ以外は横線を自由に置くことができます。ということで、次のようになります。
$memo[w-1-(j+1)]×memo[j-1]×dp[i-1][j]$

ということで、この3つの式の和が $dp[i][j]$ の値になります。
これを計算していくと、答えが $dp[h][k-1]$ にあります。