水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

No.133 カードゲーム

回答

最初のやつ
#56598 No.133 カードゲーム - yukicoder

改良版
#56599 No.133 カードゲーム - yukicoder

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;
}