AOJ 2335 - １０歳の動的計画 - ツバサの備忘録

解法

縦方向が $N$ 、横方向が $M$ とします(多分問題と逆…？)
移動は必ず全体で $N + M + 2K$ 回になります。
縦に $i$ 回、横に $K-i$ 回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのが $N + 2i$ 回、横方向が $M + 2(K-i)$ 回になるので、先にその方向を決め打つと、
$_{N + M + 2K}C_{N + 2i}$
通りになります。
あとは、縦横独立に考えることができるので、
$_{N + M + 2K}C_{N + 2i} \times (縦方向の移動パターン) \times (横方向の移動パターン)$
を計算すれば、答えになります。
ここからは縦について、つまり元の長さが $N$ で、 $i$ 回寄り道することを考えます。横方向についても同様に計算できます。
座標が負になることを許容すると、全体で $_{N + 2i}C_{i}$ 通りになります。
ここから、

$j$ 回目に寄り道をした結果、初めて座標が負になる移動の仕方

を $1 \leqq j \leqq i$ について計算し、全体から引けば、求めたい移動パターン数になります。
$j$ 回目に寄り道をして、初めて座標が負になるには、
$(正方向に移動した回数) \geqq (負方向に移動した回数)$ を満たしながら、
正負ともに $j-1$ 回ずつ移動し、その後負に移動する、という道筋をたどるしかありません。
これは、 $p$ 番目のカタラン数を $Cat_{p}$ と表記すると、 $Cat_{j-1}$ です。
そして、その後は自由に移動できるので、 $_{N +2(i-j) + 1}C_{N + i - j + 1}$ 通りあります。
よって、 $j$ 回目に寄り道をした結果初めて負になる場合の移動パターン数は、
$Cat_{j-1} \times _{N +2(i-j) + 1}C_{N + i - j + 1}$
であり、求めたかった、縦の移動パターン数は、
$_{N + 2i}C_{i} - \sum_{j = 1}^{i}(Cat_{j-1} \times _{N +2(i-j) + 1}C_{N + i - j + 1})$
となります。
あとは、これを最初の方で求めた式に当てはめれば、答えが求まります。