ABC 318

Table of Contents

D - General Weighted Max Matching

$N$ が奇数のとき、頂点を一つ追加してその頂点との辺の重みは $0$ としても結果は変わらない。よって以後 $N$ は偶数として扱う。

2頂点ずつ $N/2$ 組に分ける組み合わせの数は

$$ \frac{\binom{n}{2} \times \binom{n-2}{2} \times \cdots \times \binom{2}{2}}{2^{N/2} (N/2)!} $$

である。$N=16$ のとき $\displaystyle \frac{16!}{2^8 8!} = 2,027,025$ なので全探索しても十分間に合う。

実装をどうするかを考える。まずは $N = 4$ という具体例について考えてみる。 このときの分け方は次の3通りが考えられる。

これより

という再帰関数を書けば全探索ができる。

ll N, m;
vvll D(16, vll(16, 0));
ll ans = 0;

void dfs(int state, int depth, ll sum) {
    if (depth == (N + 1) / 2) {
        chmax(ans, sum);
    }

    int l = 0;
    rep(i, m) if (!(state & (1 << i))) {
        l = i;
        state ^= (1 << i);
        break;
    }

    rep2(i, l + 1, m) {
        if (!(state & (1 << i))) {
            state ^= (1 << i);
            dfs(state, depth + 1, sum + D[l][i]);
            state ^= (1 << i);
        }
    }
}

void solve() {
    cin >> N;

    m = N + N % 2;
    rep(i, N) {
        rep2(j, i + 1, N) {
            cin >> D[i][j];
        }
    }

    dfs(0, 0, 0);

    cout << ans << endl;
}

E - Sandwiches

https://atcoder.jp/contests/abc318/tasks/abc318_e

数字ごとに現れる index を昇順に持っておく。 $A_i = x$ となる index が $p_1, \cdots, p_m$ であるとする。 $p_k < i < p_{k+1}$ の区間にある数字は $x$ とは異なるから、この区間の数字が真ん中となる ($A_j$ として選ぶ) 場合の数は、この区間より左にある $A_i = x$ となる個数とこの区間より右にある $A_i = x$ となる個数と、真ん中の区間の個数の積である。

よって両端が $x$ であるような場合の数は

$$ \sum_{k=1}^{m-1} k \times (m-k) \times (p_{k+1} - p_k - 1) $$

である。 これを全ての数字に対して求めて和を取ると答えになる。

void solve() {
    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    map<ll, vll> mp;
    rep(i, N) {
        mp[A[i]].push_back(i);
    }

    ll ans = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        auto v = it->second;
        if (v.size() < 2)
            continue;

        rep(i, v.size() - 1) {
            ans += (v[i + 1] - v[i] - 1) * (i + 1) * (v.size() - i - 1);
        }
    }
    cout << ans << endl;
}