ARC 116

Tue, May 27, 2025

A. Odd vs Even

https://atcoder.jp/contests/arc116/tasks/arc116_a

B. Products of Min-Max

https://atcoder.jp/contests/arc116/tasks/arc116_b

考えたこと

ものすごく複雑なコードになってしまったが自力 AC. 解説放送見たらもっとスマートに解いてた。

$O(N^2)$ 解法であれば数列 $A$ をソートして $i < j$ なる $(i,j)$ の組み合わせに対して $A_i A_j (2^{j-i-1} - 1)$ ひたすら計算して足していく、最後に $A_i^2$ を足せばいいかなと思った。

つまり

\begin{align*} \sum_{i<j} A_i A_j (2^{j-i-1} - 1) + \sum_{i} A_i^2 \end{align*}

解説はこれをうまいこと変形して計算するスマートな方法でやっていた。

解説のような方法は思いつかなかったので出てくる数字の種類数とその数字の数をもとに考えることにした。

$A$ に含まれる数字が $M$ 種類あるとし、要素を $x_i$ は $x_1 < x_2 < \cdot < x_M$ とし、$x_i$ が現れる個数を $n_i$ とする。

$x_1$ が最小になり、$x_2$ が最大になるような部分集合の個数は、少なくとも1つの $x_1$ と少なくとも1つの $x_2$ を含む部分集合の個数であるから $(2^{n_1} - 1)(2^{n_2} - 1)$ 通りある。よって $x_1$ が最小になり、$x_2$ が最大となるような部分集合由来の寄与分は

$$x_1 x_2 (2^{n_1} - 1)(2^{n_2} - 1)$$

である。

$x_1$ が最小になり、$x_3$ が最大になるような部分集合の個数は、少なくとも1つの $x_1$、任意の個数の $x_2$、少なくとも1つの $x_3$ を含む部分集合の個数であるから $(2^{n_1} - 1) \times 2^{n_2} \times (2^{n_3} - 1)$ 通りある。よってこれからの寄与分は

$$x_1 x_3 (2^{n_1} - 1) \times 2^{n_2} \times (2^{n_3} - 1)$$

である。

同様にして $x_1$ が最小になり、$x_i$ が最大になるような部分集合からの寄与分は

$$x_1 x_i (2^{n_1} - 1) \times 2^{n_2} \times \cdots \times 2^{n_{i-1}} \times (2^{n_i} - 1)$$

である。

よって最大値、最小値が異なるようなとき $x_1$ が最小になるような部分集合からの寄与分を $S_1$ とすると

\begin{align*} S_1 = x_1 x_2 (2^{n_1} - 1)(2^{n_2} - 1) + \sum_{i=3}^{M} x_1 x_i (2^{n_1} - 1) \times 2^{n_2} \times \cdots \times 2^{n_{i-1}} \times (2^{n_i} - 1) \end{align*}

同様に $x_2$ が最小になるときの寄与分を $S_2$ とすると

\begin{align*} S_2 = \frac{S_1 - x_1 x_2 (2^{n_1} - 1)(2^{n_2} - 1)}{x_1 (2^{n_1} - 1) \times 2^{n_2}} \times x_2 (2^{n_2} - 1) \end{align*}

となる。

一般に $S_i$ について

\begin{align*} S_i = \frac{S_{i-1} - x_{i-1} x_{i} (2^{n_{i-1}} - 1)(2^{n_i} - 1)}{x_{i-1} (2^{n_{i-1}} - 1) \times 2^{n_i}} \times x_i (2^{n_i} - 1). \end{align*}

これを $i=M$ まで計算して最後に最大最小が同じ数字のときの寄与分 $x_i^2 (2^{n_i} - 1)$ を足せば答えになる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> mp;
    for (ll a : A) mp[a]++;

    vector<mint> num;
    vll cnt;
    for (auto [k, v] : mp) {
        num.push_back(k);
        cnt.push_back(v);
    }

    vector<mint> _two_pow;
    {
        int mx = *max_element(all(cnt));
        _two_pow.resize(mx + 1);
        _two_pow[0] = 1;
        rep2(i, 1, mx + 1) {
            _two_pow[i] = _two_pow[i - 1] * 2;
        }
    }

    auto two_pow = [&](int i) -> mint {
        return _two_pow[cnt[i]];
    };

    mint ans = 0;
    int m = cnt.size();
    rep(i, m) {
        // 同じ数字だけで構成される部分集合のとき
        ans += (_two_pow[cnt[i]] - 1) * num[i] * num[i];
    }

    if (m == 1) {
        cout << ans.val() << endl;
        return;
    }

    mint sum = 0, tmpsum = 0;
    sum = tmpsum = num[0] * (two_pow(0) - 1) * num[1] * (two_pow(1) - 1);
    rep2(i, 2, m) {
        tmpsum /= num[i - 1] * (two_pow(i - 1) - 1);
        tmpsum *= two_pow(i - 1);
        tmpsum *= num[i] * (two_pow(i) - 1);
        sum += tmpsum;
    }

    ans += sum;
    rep2(i, 1, m) {
        sum -= num[i - 1] * (two_pow(i - 1) - 1) * num[i] * (two_pow(i) - 1);
        sum /= num[i - 1] * (two_pow(i - 1) - 1) * two_pow(i);
        sum *= num[i] * (two_pow(i) - 1);
        ans += sum;
    }
    cout << ans.val() << endl;
}

解説放送の方針版

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));

    mint ans = 0;
    mint sum = 0;
    for (int i = N - 2; i >= 0; i--) {
        sum *= 2;
        sum += A[i + 1];
        ans += sum * A[i];
    }

    rep(i, N) {
        ans += (mint)A[i] * A[i];
    }

    cout << ans.val() << endl;
}