メンバー > SGHR > topcoder > 同じ数字で挟み撃ち


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題


ジャンル

??

解説

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.に戻る。

コード

  1. #include<cmath>
  2. #include<cstdlib>
  3. #include<string>
  4. #include<sstream>
  5. #include<vector>
  6. #include<iostream>
  7. #include<queue>
  8. #include<deque>
  9. #include<map>
  10. #include<set>
  11. #include<stack>
  12. #include<list>
  13. #include<algorithm>
  14. using namespace std;
  15.  
  16. int n = 11;
  17. int ans = 0;
  18.  
  19. void rec(int i, vector<int> cards){
  20. /*
  21.   for(int j=0; j<2*n; j++){
  22.   cout << cards[j] << " ";
  23.   }
  24.   cout << endl;
  25.   */
  26. if(i == n+1){
  27. for(int j=0; j<2*n; j++){
  28. cout << cards[j] << " ";
  29. }
  30. cout << endl;
  31. ans++;
  32. }
  33. else{
  34. for(int j=0; j<2*n; j++){
  35. if(j+i+1 <= 2*n-1){
  36. if(cards[j] == 0 && cards[j+i+1] == 0){
  37. cards[j] = i;
  38. cards[j+i+1] = i;
  39. }
  40. else continue;
  41. }
  42. else break;
  43. rec(i+1, cards);
  44. cards[j] = 0;
  45. cards[j+i+1] = 0;
  46. }
  47. }
  48. }
  49.  
  50. int main(){
  51. vector<int> cards;
  52. cards.resize(2*n);
  53. for(int i=0; i<2*n; i++) cards[i] = 0;
  54. rec(1, cards);
  55. cout << ans << endl;
  56. }
  57.