メンバー/SGHR/topcoder/同じ数字で挟み撃ち - 阪大理学部科学計算・開発サークル -Circle for Science Caluculation and Development-

問題

ジャンル

??

解説

1からnまでの数字が書かれたカードが2枚ずつ全部で2n枚あり、iとiの間のカードがi枚になるような順列の数を数えよ、という問題。
n=11だと総当りは無理だったのでアルゴリズムを以下のように工夫した。
ちなみに答えは（逆順も含めて）35584通りだった。そんなにあるのか。

1.ある数字iのおく場所jを決める。
2.場所j+i+1にiがおけるか判定する。
3.おければiを1増やして1.に戻る。おけなければjを1増やして1.に戻る。

コード

#include<cmath>
#include<cstdlib>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;
 
int n = 11;
int ans = 0;
 
void rec(int i, vector<int> cards){
  /*
  for(int j=0; j<2*n; j++){
    cout << cards[j] << " ";
  }
  cout << endl;
  */
  if(i == n+1){
    for(int j=0; j<2*n; j++){
      cout << cards[j] << " ";
    }
    cout << endl;
    ans++;
  }
  else{
    for(int j=0; j<2*n; j++){
      if(j+i+1 <= 2*n-1){
	if(cards[j] == 0 && cards[j+i+1] == 0){
	  cards[j] = i;
	  cards[j+i+1] = i;
	}
	else continue;
      }
      else break;
      rec(i+1, cards);
      cards[j] = 0;
      cards[j+i+1] = 0;
    }
  }
}
 
int main(){
  vector<int> cards;
  cards.resize(2*n);
  for(int i=0; i<2*n; i++) cards[i] = 0;
  rec(1, cards);
  cout << ans << endl;
}