結果

問題 No.133 カードゲーム
コンテスト
ユーザー 今野博晴
提出日時 2020-08-01 09:25:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,533 bytes
コンパイル時間 603 ms
コンパイル使用メモリ 66,256 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 15:25:14
合計ジャッジ時間 1,335 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

#include <cstring>

using std::cin;
using std::cout;
using std::endl;

using std::memcpy;

static int N, A[4], B[4];
static int CN, CA[4*3*2*1+1][4], CB[4*3*2*1+1][4];

static void
make_combination_0(int val[4], int comb[][4], bool used[4], int n)
{
  for (int i = 0; i < N; i++)
  {
    if (!used[i])
    {
      used[i] = true;
      comb[CN][n] = val[i];
      if (n + 1 < N)
      {
        make_combination_0(val, comb, used, n + 1);
      }
      else
      {
        memcpy(comb[CN + 1], comb[CN], sizeof(int) * 4);
        CN++;
      }
      used[i] = false;
    }
  }
}

static void
make_combination(int val[4], int comb[][4])
{
  bool used[4] = {false};
  CN = 0;
  make_combination_0(val, comb, used, 0);
}

static bool
final_win(int a[], int b[])
{
  int win = 0;
  for (int n = 0; n < N; n++)
  {
    if (b[n] < a[n])
    {
      win++;
    }
  }
  return N < win * 2;
}

// 最終的な勝率。これが single_win_rate と一致するのかどうかを知りたい。
static double
final_win_rate()
{
  make_combination(A, CA);
  make_combination(B, CB);
  int win = 0;
  for (int ia = 0; ia < CN; ia++)
  {
    for (int ib = 0; ib < CN; ib++)
    {
      if (final_win(CA[ia], CB[ib]))
      {
        win++;
      }
    }
  }
  return double(win) / (CN * CN);
}

static double
solve()
{
  return final_win_rate();
}

int
main()
{
  cin >> N;
  for (int n = 0; n < N; n++)
  {
    cin >> A[n];
  }
  for (int n = 0; n < N; n++)
  {
    cin >> B[n];
  }
  cout << solve() << endl;
  return 0;
}
0