「 今週のお題：隣り合えないカップル」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力から与えられる$n$に対して、$n$組の男女のカップルを円形に並べる方法が何通りあるか出力する。
- ただし、必ず男女が交互に配置されること。また、どのカップル同士も隣り合わないこと。
- 回転して同じ配置になる並べ方は重複して数えない。しかし反転して同じになる場合は区別する。
解説
ひとまずは、男性の配置を決めてしまいます。これは円順列として、$(n-1)!$通りあります。
そうしてから、位置に従って配置した男性にIDを振れば ( カップルの女性にも同じIDを振る )、残った女性をどう配置するか、の問題で済みます。( その配置の数に $(n-1)!$ をかければ答えになります )
じゃあ、女性の配置の仕方をどう考えるか…ですが。ちょっとうまい方法が見つからなかったのですね。
女性のIDと空いている位置のID ( こっちは 0 開始にしています ) の差 ( ただし $mod\,\,n$ で考える ) が 1,2 になってはいけないということで、順列の満たすべき条件は分かっているので、全順列を調べれば済むのですが。今回は $n$ の上限が 7 となっているので、全部調べてもそう大した時間はかかりません。
…で、結局提出したのは、その全順列を調べる実装でした。
n=gets.to_i
p (1..n-1).reduce((1..n).to_a.permutation.count{|r|r.each_with_index.all?{|e,i|(e-i-1)%n>1}},&:*)
終わりに
ibeckuuさんの解説記事 に、数学的な解法の紹介がありました。
また、そのものズバリの数列はOEISのA059375にも載っています。
うーむ。今回は、わたしまけましたわ、的でちょっとくやしい所。
