結果

問題 No.173 カードゲーム（Medium）
ユーザー togatogatogatoga
提出日時 2015-03-29 10:25:49
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,202 bytes
コンパイル時間 1,361 ms
コンパイル使用メモリ 107,364 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-17 00:01:37
合計ジャッジ時間 15,354 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 682 ms
4,380 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 1,298 ms
4,380 KB
testcase_06 AC 1,216 ms
4,380 KB
testcase_07 AC 1,150 ms
4,380 KB
testcase_08 AC 1,146 ms
4,380 KB
testcase_09 AC 1,608 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits.h>
#include <bitset>

#include <tuple>
#include <unordered_map>
#include <random>

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-9;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
double Pa, Pb;
vector<int> A, B;
bool usedA[22];
bool usedB[22];
unsigned long xor128(void) {
  static unsigned long x = 123456789, y = 362436069, z = 521288629,
                       w = 88675123;
  unsigned long t;
  t = (x ^ (x << 11));
  x = y;
  y = z;
  z = w;
  return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
int getMinA(const vector<int> &array) {
  for (int i = 0; i < array.size(); i++) {
    if (usedA[i])
      continue;
    usedA[i] = true;
    return array[i];
  }
  return 0;
}
int getMinB(const vector<int> &array) {
  for (int i = 0; i < array.size(); i++) {
    if (usedB[i])
      continue;
    usedB[i] = true;
    return array[i];
  }
  return 0;
}

int main() {
  cin >> N >> Pa >> Pb;
  A.resize(N);
  B.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());

  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  sort(B.begin(), B.end());
  int res = 0;
  for (int i = 0; i <= 100000; i++) {
    memset(usedA, false, sizeof(usedA));
    memset(usedB, false, sizeof(usedB));
    int sumA, sumB;
    sumA = sumB = 0;
    random_device rd;
    mt19937 gen(rd());
    for (int i = 0; i < N; i++) {
      int cardA, cardB;
      cardA = cardB = 0;
      if (i != N - 1) {
        uniform_real_distribution<double> randomDoubleDistribution(0.0, 1.0);
        double proA = randomDoubleDistribution(gen);
        double proB = randomDoubleDistribution(gen);
        if (proA <= Pa) {
          cardA = getMinA(A);
        } else {
          vector<pii> tmpA;
          for (int k = 0; k < N; k++) {
            if (usedA[k])
              continue;
            tmpA.push_back(mp(k, A[k]));
          }
          pii pa = tmpA[xor128() % tmpA.size()];
          usedA[pa.first] = true;
          cardA = pa.second;
        }
        if (proB <= Pb) {
          cardB = getMinB(B);
        } else {
          vector<pii> tmpB;
          for (int k = 0; k < N; k++) {
            if (usedB[k])
              continue;
            tmpB.push_back(mp(k, B[k]));
          }
          pii pb = tmpB[xor128() % tmpB.size()];
          usedB[pb.first] = true;
          cardB = pb.second;
        }
      }else{
        cardA = getMinA(A);
        cardB = getMinB(B);
      }
      if (cardA > cardB){
        sumA += (cardA + cardB);
      }else if(cardB > cardA){
        sumB += (cardA + cardB);
      }
    }
    if (sumA > sumB){
      res++;
    }
  }
  printf("%.9lf\n", (double)res / 100000);
  return 0;
}
0