school competition 2 [技術室奥プログラミングコンテスト#4 Day1 I]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6665447

制約に弱点があり、2^N,2^Mが可能であるため、チーム分けについては全通り試せそう。
anmichi校でのチーム分けに対して、sanada校のチーム分けで条件を満たすものの確率を全て足すことで答えを求めていこう。
anmichi校のチーム分けでAの総和がaであるとき、sanada校のAの総和aaが満たすべき条件は、
(1) aa < a
(2) sanada_tot - aa < anmichi_tot - a
(2)より
(3) sanada_tot - anmichi_tot + a < aa
(1),(3)より
sanada_tot - anmichi_tot + a < aa < aとなる。
よって、これを満たすaaの個数が分かれば、確率はaa_cnt/aa_all_cntとなる。
これを二分探索とかで求めると答えが得られる。

int N, M, A[20], B[20];
vector<ll> sanada;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    ll anmichi_tot = 0;
    rep(i, 0, N) anmichi_tot += A[i];
    ll sanada_tot = 0;
    rep(i, 0, M) sanada_tot += B[i];

    rep(msk, 0, 1 << M) {
        ll a = 0, b = 0;
        int acnt = 0, bcnt = 0;
        rep(i, 0, M) {
            if (msk & (1 << i)) a += B[i], acnt++;
            else b += B[i], bcnt++;
        }
        if (0 < acnt and 0 < bcnt and a > b) sanada.push_back(a);
    }
    sort(all(sanada));
    sanada.push_back(infl);

    double ans = 0;
    rep(msk, 0, 1 << N) {
        ll a = 0, b = 0;
        int acnt = 0, bcnt = 0;
        rep(i, 0, N) {
            if (msk & (1 << i)) a += A[i], acnt++;
            else b += A[i], bcnt++;
        }
        if (0 < acnt and 0 < bcnt and a > b) {
            ll lft = sanada_tot - anmichi_tot + a;
            ll rht = a;
            
            auto lft_ite = upper_bound(all(sanada), lft);
            auto rht_ite = lower_bound(all(sanada), rht);

            int aa_cnt = rht_ite - lft_ite;
            int aa_all_cnt = sanada.size() - 1;
            if(0 < aa_cnt) chmax(ans, 1.0 * aa_cnt / aa_all_cnt);
        }
    }
    printf("%.10f\n", ans);
}