Max-Min Sums [AtCoder Beginner Contest 151 E]

https://atcoder.jp/contests/abc151/tasks/abc151_e

解説

https://atcoder.jp/contests/abc151/submissions/9477762

考察に行き詰まったときは、何か全探索できそうな対象を探す。
選び方の全探索は難しそうなので、他に問題文にあることで全探索できるものはないだろうか。

• 整数A[i]
• maxX
• minX

これくらいしか思いつかない。
整数A[i]を固定しても、maxXもminXも確定しないので、あまりうれしくない。
maxXを固定して考えると、集合Xについて「A[i]=maxXを1つは含む、かつ、他の要素はmaxX以下」であることが言える。
この仮定は嬉しいように感じる。
それっぽいものが見つかったので、この方針で考えてみよう。
だが、maxXで全探索すると、同じA[i]が存在する時にちょっと考えなきゃいけないので、以下のように全探索をする。
Aを昇順ソートしておき、A[i]を全探索する。
この時、集合XにA[i]が必ず入っていて、他の要素はi番目より前の要素から構成されていることを考える。

ここで、発想の転換が必要になる。
今流行りの主客転倒テクの発想が役に立つ。
全部のmaxX-minXを考えてみると、maxXの総和-minXの総和が答えになる。
maxXの総和を求めるには、あるmaxX×その組み合わせで求めることができるが、
maxXとなる集合Xの組み合わせは、先程の全探索方法を考えると、i番目より前の要素からK-1を選ぶ組み合わせとなる。
これはComb(i, K-1)と等しいので簡単に計算可能。
よって、minX, maxXの総和がそれぞれ計算可能なので、解くことができる。

int N, K, A[101010];
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    
    mint maxX = 0;
    sort(A, A + N);
    rep(i, K - 1, N) maxX += mint(A[i]) * com.aCb(i, K - 1);

    mint minX = 0;
    sort(A, A + N, greater<int>());
    rep(i, K - 1, N) minX += mint(A[i]) * com.aCb(i, K - 1);

    mint ans = maxX - minX;
    cout << ans << endl;
}