CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第85回「隣り合えないカップル」

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り、

${n}$ 組のカップルを男女交互に円形に並べる事を考える。
カップルが隣同士に並ばないパターンの総数を解答する。
円形なので回転したものは同じと見なすが、逆順は別とカウントする。
${n \leq 7}$

方針

メモ化再帰を用いる
人数 ${n}$ 人の女子を円形に並べ、その間にカップルが隣りあわない様に ${n}$ 人の男子を並べる配置を考える。
女子の組 ${\{g0,g1...g(n-1)\}}$ と添え字番号が同じ男子の組 ${\{b0,b1...b(n-1)\}}$ をカップルとして、添え字 ${i}$ と ${i+1}$ ( ${n-1}$ 番目は ${n-1}$ と1周して ${0}$ )以外の位置に男子 ${bi}$ を配置する全パターンをメモ化再帰により数える。
これに、女子の円順列の総数 ${(n-1)!}$ を掛けて解答とする