AtCoder Beginner Contest 265 E問題 Warp

座標平面の原点にコマがある. このコマに対して, 以下の3種類の操作から1つを選び, 実行することを $N$ 回繰り返す.

ただし, 移動後にコマが $(X_1, Y_1), \dots, (X_M, Y_M)$ のどれかに一致するような移動はできない.

$N$ 回の移動経路は何通りか?

説明のため, 3種類の移動を上から順に移動1, 移動2, 移動3ということにする. また, $v_1=(A,B), v_2=(C,D), v_3=(E,F)$ とする.

動的計画法で求めることにする.

$n=0,1,2, \dots, N$ 及び $p,q,r=0,1, \dots, n$ に対して, ${\rm DP}[n,p,q,r]$ を

このとき, $p+q+r=n$ という条件が働くことから, $r=n-p-q$ である. よって, 動的計画法の次元を1減らすことができる. 以降では記号のら濫用にはなるが ${\rm DP}[n,p,q]$ で同様の意味を表すとする.

ベース条件は $n=0$ のときで ${\rm DP}[0,0,0]=1$ である.

$n \geq 1$ のとき, 遷移式は $0 \leq p+q \leq n-1$ のとき, $r:=(n-1)-(p+q)$ として, 移動の方法による場合分けを行う.

$(p+1) v_1+q v_2+r v_3 \not \in S$ ならば ${\rm DP}[p+1, q]$ に ${\rm DP}[p,q ]$ を加算する.
$p v_1+(q+1) v_2+r v_3 \not \in S$ ならば ${\rm DP}[p, q+1]$ に ${\rm DP}[p,q ]$ を加算する.
$p v_1+q v_2+(r+1) v_3 \not \in S$ ならば ${\rm DP}[p, q]$ に ${\rm DP}[p,q ]$ を加算する.