ARC116 振り返りメモ(B問題まで)

#結果
Aの1完で, レート変化は729→713 (-16)

#A問題 ( Odd vs Even )
###概要

N の約数のうち, 偶数のものと奇数のものの個数を比較する.

###方針
N を素因数分解することを考えると,

N = 2^d \times a　(aは奇数)

という風に素因数分解できるはずである.
d = 0のときは, 奇数の約数しか持たないので, 当然奇数の約数の方が多い.
d = 1のときは, 奇数と偶数の約数の個数は等しくなる.
d > 2のときは, 偶数の約数の方が多くなる.

まとめると, 4で割った余りが1または3のときは奇数の方が多くなり, 2のときは等しくなり, 0の時は偶数の方が多くなる.

C++ での実装例は以下のようになる.

a.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    ll t; cin >> t;
    rep(i, t) {
        ll n; cin >> n;
        if (n % 4 == 1 || n % 4 == 3) cout << "Odd" << endl;
        if (n % 4 == 0) cout << "Even" << endl;
        if (n % 4 == 2) cout << "Same" << endl;
    }
    return 0;
} 

#B問題 ( Products of Min-Max )
###概要

長さNの整数列(A)の空でない全ての部分列(B)に対して, それぞれmax(B) * min(B) を計算し, その総和を求める.

方針

minの添字をi, maxの添字をjとすると,
A[i] * A[j] * 2 ^ (j - i - 1)
を全ての(i, j)の組について計算すれば良い.
が, 愚直に計算するとO(N^2)となって計算が間に合わなくなってしまう.
そのため, i を固定して, jをi+1~n まで動かす部分をまとめて計算する.

C++ での実装例は以下のようになる.

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

const ll MOD = 998244353;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    ll ans = 0;
    // max と min が同じ値の場合の処理
    rep(i, n) {
        ans += a[i] * a[i] % MOD;
    }
    ll mx = 0;
    for (ll i = 1; i < n; i++) {
        mx = 2 * mx;
        mx += a[n-i];
        mx %= MOD;
        ans += a[n-i-1] * mx % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}