ABC011 D - 大ジャンプ

D - 大ジャンプ
提出コード
まずはゴールにいくために最低何回、上下左右に移動するかを調べる必要があります。
この問題では上下、左右は反転しても何ら問題がないので、X、Yの入力は最初の時点で正に直してしまって問題ありません。
ということで、上下、左右に移動する最低回数はそれぞれ、
Y/DとX/Dになります。
この時点で割り切れなかった場合、およびN回をオーバーしてしまった場合、どう頑張ってもゴールにたどり着けないので答えは0になります。
次に、残った移動回数でどうするべきか、ということについて考えると、
上下、もしくは左右を1セットとすることで、同じ地点に居座り続けることができます。
なので、(N-X/D-Y/D)/2回、上下、もしくは左右に移動します。
もしこのセットを実行できない、つまり(N-X/D-Y/D)が2で割り切れない場合、答えは0になります。
あとは、うまいこと確率を計算する方法を求めます。
期待値の線形性を利用し、全探索をすると、うまくいきます。
先ほどいった上下、もしくは左右に動かすパターンを、上下にi回、左右はその残り、とすると、
上下はY/D+iとi、左右はX/D+(N-X/D-Y/D)/2-i、(N-X/D-Y/D)/2-i回ずつ移動することになります。
あとはこの4種類の並べ方を、全事象であるで割ることでこのときの確率を求めることができます。
最後に、iを0から最大値までで全探索し、それぞれの確率を足し合わせてあげれば、最終的な答えを求めることができます。
上下左右をそれぞれp,q,r,s回移動するもの、とするとそのときの並べ方は

で求めることができます。これを頑張ってうまくコードに落とし込むことができれば完成です。