私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「隣り合えないカップル」（CodeIQ）を参照してください。
n 組のカップルがいます。
全員を円形に並べるとき、各カップルは隣同士にならないようにします。
ただし、男女は交互に並ぶようにしたいと思います。
例えば、n=3のとき、図のような2通りの並べ方があります。
（同じ数字がカップル、M、Fは性別をイメージしています。）
※円形なので回転した位置は一つとカウントしますが、逆順は別々にカウントします。
M1 F2 F3 M3 M2 F1
M1 F3 F2 M2 M3 F1
【問題】
標準入力から n が与えられるとき、並べ方が何通りあるか求め、そのパターン数を標準出力に出力してください。
※最大で7組まで求められるようにしてください。
C++で解答しています。
#include <stdio.h>
#include <stdlib.h&ht;
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// デバッグ出力用
void printVector(const vector<int>& v){
for(auto i: v){
printf("%d ", i);
}
printf("\n");
}
/**
* 並び順の正しさをチェックする。
* @param m 男性の並び順
* @param w 女性の並び順
* @return 1：カップルが隣合わない、0：カップルが隣り合う
*/
int check(const vector<int>& m, const vector<int>& w){
for(int i=0; i<m.size(); i++){
int l = i ? i-1 : m.size()-1;
int r = i;
if ((m[i] == w[r]) || (m[i] == w[l])){
return 0;
}
}
return 1;
}
/**
* 組み合わせ数を求める。
* @param n カップルの数
* @return 組み合わせ数
*/
int getPatternCount(int n){
// 男性の基本パターン
vector<int> Man(n-1);
iota(Man.begin(), Man.end(), 2);
vector<int> Woman(n);
iota(Woman.begin(), Woman.end(), 1);
int ret = 0;
do{
vector<int> v = {1};
copy(Man.begin(), Man.end(), back_inserter(v));
// printVector(v);
do{
ret += check(v, Woman);
}while(next_permutation(Woman.begin(), Woman.end()));
}while(next_permutation(Man.begin(), Man.end()));
return ret;
}
int main(void){
char str[8] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
int n = atoi(str);
int ret = getPatternCount(n);
printf("%d\n", ret);
}
return 0;
}
C++で解答しています。
C++を使っているということは力技でやっているコードになります。
配列は単純に考えると男性の円順列と女性の順列を組み合わせて両隣に同じ数字が来なければ良いということになります。実際のコードもそのような処理になっています。
41〜42行目で男性2〜nのベクターを作っています。2以降なのは先頭を1に固定できるためです。44〜45行目で女性1〜nのベクターを作ります。
49〜56行目のループで男性のベクターから順列を生成し、53〜55行目のループで女性の順列を生成しています。これで総当たりになります。
51行目の処理は男性の先頭に1番を追加するためのもので、これによって男性の並びは円順列として順次生成されることになります。
男性の並び順と女性の並び順を引数にもらい、男性の両隣の女性の番号をチェックして同じ番号でなければ1、同じ番号があれば0を返します。問題の条件に合致する場合に1が返り、ダメな場合は0が買えるのでこの関数の戻り値を足し合わせれば組み合わせ数が求まります。
最大のnが7なので組み合わせ数は6!×7!=3628800です。そんなに大した数ではないので強引にやってしまいました。本当は動的計画法などを使ってやるのが模範解答でしょうか？