Submission #1690934

---

Source Code Expand

// 基本テンプレート

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

double rec[35][35], p;
int N;
int mat[35][35];
int comb[35][35];

struct Elem {
    int win, rank;
    bool operator<(const Elem &a) const {
        if(win != a.win) return win > a.win;
        return rank < a.rank;
    }
};

vector<Elem> vs;

double func(int a, int b) {
    return 1.0 * comb[a][b] * pow(p, b) * pow(1-p, a-b);
}

double calc(int s, int t) {
    int ma = max(s, t);
    double ret = 0.0;
    repq(u,0,ma) {
        double a = (s < u ? 0.0 : func(s, u));
        double b = ((N-1-s)-(t-u) < 0 ? 0.0 : func(N-1-s, (N-1-s)-(t-u)));
        ret += a * b;
    }
    return ret;
}

double solve(int a, int b) {
    if(rec[a][b] != -1) return rec[a][b];
    if(a == N-1) {
        double val = calc(vs[a].win, b);
        if(b > 0) val += solve(a, b-1);
        return rec[a][b] = val;
    }
    else {
        int rank_a = vs[a].rank, rank_b = vs[a+1].rank;
        int win_orig = vs[a].win;
        double val = 0.0;
        repq(k,0,b) {
            double x = calc(win_orig, k);
            double y = solve(a+1, k-(rank_a>rank_b));
            val += x * y;
        }
        return rec[a][b] = val;
    }
}

signed main() {
    rep(i,0,35) comb[i][0] = 1;
    rep(i,1,35) repq(j,1,i) {
        comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
    }

    scanf("%lld", &N);
    int a, b;
    scanf("%lld/%lld", &a, &b);
    p = (double) a / b;
    rep(i,0,N) rep(j,0,N) cin >> mat[i][j];
    rep(i,0,N) rep(j,0,N) rec[i][j] = -1;

    rep(i,0,N) {
        int rank = i, win = 0;
        rep(j,0,N) win += mat[i][j];
        vs.push_back(Elem{win, rank});
    }
    sort(vs.begin(), vs.end());

    printf("%.12f\n", solve(0, N-1));
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:102:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &N);
                      ^
./Main.cpp:104:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld/%lld", &a, &b);
                               ^

Judge Result