読者です 読者をやめる 読者になる 読者になる

「 今週のお題:隣り合えないカップル」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力から与えられる$n$に対して、$n$組の男女のカップルを円形に並べる方法が何通りあるか出力する。
  • ただし、必ず男女が交互に配置されること。また、どのカップル同士も隣り合わないこと。
  • 回転して同じ配置になる並べ方は重複して数えない。しかし反転して同じになる場合は区別する。

解説

ひとまずは、男性の配置を決めてしまいます。これは円順列として、$(n-1)!$通りあります。

そうしてから、位置に従って配置した男性にIDを振れば ( カップルの女性にも同じIDを振る )、残った女性をどう配置するか、の問題で済みます。( その配置の数に $(n-1)!$ をかければ答えになります )

f:id:ange1:20160324040235p:plain

じゃあ、女性の配置の仕方をどう考えるか…ですが。ちょっとうまい方法が見つからなかったのですね。

女性の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にも載っています。

うーむ。今回は、わたしまけましたわ、的でちょっとくやしい所。