No.133 カードゲーム - 名もなき未知

問題

回答

AくんとBくんに同じ枚数のカードが配られるので，カードを出しあって勝った回数が多いものを勝者とする．（カードはランダムに出す）Aくんが勝つ確率は？
ということなのですが，カード枚数が十分に小さいため，AくんとBくんがカードを出す順序を全列挙して，全部比較して数え上げれば良いと思います．
問題のタグは順列になっていますが，総当りってイメージです，個人的には．（同じことを言っている可能性はある）

順序の組み合わせは C++の場合， next permutationで受け取れるのですが…
これの使い方が特殊で，少し戸惑いました．なんでこれで動くん…．

参考にしたサイト
【C++】next_permutationがちょうすごい件【TopCoder】 - Yoh Okunoの日記
 全ての組み合わせを作る【C++】 - Programming Magic
http://www.cplusplus.com/reference/algorithm/next_permutation/

というわけで，next permutationを使ってひたすら回します．
ところで，AとBのすべての組み合わせを考えるときに，実はAはひたすら変え，Bを動かさないでやることにより，計算量を削減することが実は可能です（解答例を見てすごいなあと思った）

改善したものから，貼っておきます・・・

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

  int N;
  cin >> N;

  int A[N];
  int B[N];
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> B[i];

  int IDXS[N];
  REP(i, N) IDXS[i] = i;

  int sum = 0;
  int win = 0;
  do {
      int twin = 0;
      REP(i, N) {
          if(A[IDXS[i]] > B[i]) twin++;
      }
      if(twin > (N - twin)) win++;
      sum++;
  } while( next_permutation(IDXS, IDXS+N) );

  cout << (double) win / sum << endl;
  return 0;
}

改善前のやつ… AもBも両方共組み合わせ作ってそのたびにループするパターン…

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

  int N;
  cin >> N;

  vector<int> A(N);
  vector<int> B(N);
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> B[i];

  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  int sum = 0;
  int win = 0;
  do {
      do {
          int twin = 0;
          REP(i, N) {
              if(A[i] > B[i]) twin++;
          }
          if(twin > (N - twin)) win++;
          sum++;
      } while( next_permutation(B.begin(), B.end()) );
  } while( next_permutation(A.begin(), A.end()) );

  cout << (double) win / sum << endl;
  return 0;
}