The Merchant Guild (UVa Live Archive Europe Southwestern 2008)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302

問題

長さnのハッシュにn個の値を線形探索で値を入れていく。もしもN-1まで開いてない場合は失敗となる。m個分はどのタイミングでどの箇所に挿入するか分かっている。全ての値を挿入できる、値の挿入の仕方は何通りか？
1<=m<=n<=300

解法

m個分の挿入タイミングは関係ないので、どこに挿入するかだけカウントしておく。次にcalc(depth, rest)を後ろから計算していく。depthは現在の位置で、restは現在までに何個の空きがあったかを表していて、前もって挿入された分はそこに来たタイミングでrestから引いておく。途中でrestが負になったら失敗とみなす。コンビネーションの計算を前処理しておけば、このcalcはメモ化再帰でO(n^3)で計算可能。