結果

問題 No.133 カードゲーム
ユーザー 23k_h23k_h
提出日時 2021-03-18 02:23:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 5,744 bytes
コンパイル時間 2,006 ms
コンパイル使用メモリ 182,828 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-27 16:41:09
合計ジャッジ時間 2,745 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
 
#define SIZE(x) ((ll)(x).size()) 
#define MAX(x) *max_element(ALL(x)) 
#define MIN(x) *min_element(ALL(x)) 
#define ALL(x) (x).begin(),(x).end()

 
#define inf 1000000000000 
#define mod 1000000007 
#define MAXR 100000 
 
#define PB push_back
#define PF push_front 
#define MP make_pair 
#define F first 
#define S second

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void printd(double f, int n){cout << fixed << setprecision(n) << f << endl;}//指定した桁で小数を出力

void YES(bool c=true){cout<<(c?"YES":"NO")<<endl;}//YES(条件式)で記述
void Yes(bool c=true){cout<<(c?"Yes":"No")<<endl;}//YES(条件式)で記述
bool updown(ll x, ll a, ll b) {return x>=a&&x<=b;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

string upper(string s){
  transform(s.cbegin(), s.cend(), s.begin(), ::toupper);
  return s;
}

string lower(string s){
  transform(s.cbegin(), s.cend(), s.begin(), ::tolower);
  return s;
}

vector<string> split(string str, char del) {
    int first = 0;
    int last = str.find_first_of(del);
 
    vector<string> result;
 
    while (first < str.size()) {
        string subStr(str, first, last - first);
 
        result.push_back(subStr);
 
        first = last + 1;
        last = str.find_first_of(del, first);
 
        if (last == string::npos) {
            last = str.size();
        }
    }
 
    return result;
}

// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

void print_map(map<int, vector<int>> mp){//mapの出力
    auto begin = mp.begin(), end = mp.end();
    for (auto iter = begin; iter != end; iter++) {
        // first: key, second: value
        cout << "key = " << iter->first << "\n";
        cout << "value = " << iter->second.size() << "\n";
    }
}

bool vector_finder(std::vector<int> vec, int number) {//vector内の要素検索
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return true;
  }
  else { // 発見できなかったとき
    return false;
  }
}

// union by size + path having
//https://pyteyon.hatenablog.com/entry/2019/03/11/200000
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

bool is_prime(ll n){
    int a = sqrt(n);
    if(n == 1 || n == 2 || n == 3) return true;
    else{
        bool frag = true;
        FOR(i, 2, a+1){
            if(n % i == 0) frag = false;
        }
        return frag;
    }
}

vector<vector<int>> d(10, vector<int>(10));
void warshall_floyd(int n) {
  for (int k = 0; k < n; k++){       // 経由する頂点
    for (int i = 0; i < n; i++) {    // 始点
      for (int j = 0; j < n; j++) {  // 終点
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

int n;
int dfs(int now, int ca, int cb, vector<int> ad, vector<int> bd){
    if(now == n){if(ca>cb) return 1; else return 0;}
    int res = 0;
    int ta, tb; vector<int> tmpa, tmpb;
    REP(i, ad.size()) REP(j, bd.size()){
        tmpa = ad; tmpb = bd;
        ta = ca; tb = cb;
        if(tmpa[i] > tmpb[j]) ta++;
        if(tmpa[i] < tmpb[j]) tb++;
        tmpa.erase(tmpa.begin() + i); tmpb.erase(tmpb.begin()+j);
        res += dfs(now+1, ta, tb, tmpa, tmpb);
        
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<int> a(n), b(n);
    REP(i, n) cin >> a[i]; REP(i, n) cin >> b[i];
    int awin = dfs(0, 0, 0, a, b);
    int pattern = 1;
    REP(i, n) pattern *= (i+1);
    cout << (double)awin/pow(pattern, 2) << endl;
    return 0;
}

//g++ main.cpp -std=c++17 -I /home/k0gane/ac-library

//累積和
//https://qiita.com/drken/items/56a6b68edef8fc605821
//point...n+1の容量のリストを作る
//
//深さ優先...push_front
//幅優先...push_back
0