ABC149E: Handshake解説

いい問題でした。The 500点って感じ。

## 【問題概要】

N個の要素を持つ数列$ A $が与えられる。
$ \sum_{x=1}^{n} \sum_{y=1}^{n} A_x+A_y $ とし、全ての組み合わせにおいて$ A_x+A_y $を降順に並べた時、$M$番目までの総和を求めよという問題。
かなり汎用性が高そうな題材なので、無限回既出なんだろうなという気持ちになる。

$ N^2 $が最大で$ 10^{10} $ になるので、全列挙では残念ながら間に合わない。どうにか$ N^2 $かけずに組み合わせを考えたい気持ちになる。
解法を先に提示しておく。

+ $ A_x+A_y $を降順に並べた際、$ M $番目に来る数を求める
+ 操作1で求めた$M$番目の数を$K$と置いた時、$K \leqq A_x+A_y$となる数の総和を求める

（最後に調整が必要な場合もあるが）実はこの2つの操作さえ処理できればこの問題を解くことが出来る。そしてこの処理は一見$N^2$かかってしまいそうに見えるが、前者は$ O(N\log{}^2N) $、後者は$ O(N\log{}N) $で処理することが可能である。
以下、各操作について述べる。

__1. $A_x+A_y$を降順に並べた際、$ M $番目に来る数を求める__

本質を言う。
<b>真偽判定として「$ M $番目に来る数を仮にKとする。$ K \leqq A_x+A_y $となるような組み合わせの数が本当に$ M $個以上あるか？」を考え、二分探索をする。</b>
ここがわからない人に、この問題は早いかも知れない。
[これ](https://atcoder.jp/contests/arc075/tasks/arc075_b)なんかをやってまず二分探索を理解するといいと思う。

さて、ではどういったアルゴリズムを用いるかだが、$ K \leqq A_x+A_y $となる組み合わせの数が求められれば上記の真偽判定が出来ることになる。ここでは$ getCount(K) := K \leqq A_x+A_y $となる組み合わせの数、という関数を考えてみる（[はまやんさんに倣いました](https://www.hamayanhamayan.com/entry/2020/01/01/024415)）。
さて、ここでこの不等式を移項すると$ K-A_x \leqq A_y $となる。これは各$ A_x $について、$ K-A_x $よりも大きい$ A_y $の数の合計が、$ K \leqq A_x+A_y $の組み合わせの数と同値であることを意味している。

要は$ A_x $を1つ固定すると、$ K \leqq A_x+A_y $にするために必要な$ A_y $の個数が$ A_x $それぞれについてわかるということである。
で、これはAを昇順ソートしておくとlower_boundで求められる。詳細な雰囲気は以下のコードで察してほしい。

```cpp
ll get_count(ll K, const vector<ll> &a) {
    // aはソート済み
    int n = (int)a.size();
    ll ret = 0ll;
    rep(i,n) {
        // K-Axをbと置く
        ll b = K-a[i];
        auto itr = lower_bound(a.begin(), a.end(), b);
        // lower_boundで得られたイテレータを終端のイテレータから引くと
        // K-Ax以上であるAyの個数が分かるので、それを各Axについて足していく
        ret += (a.end()-itr);
    }
    return ret;
}
```

Kを二分探索する準備ができたので、やる。

```cpp
// binary search
ll ok = 0; ll ng = LINF;
while (abs(ok-ng)>1) {
    ll mid = (ok+ng)/2;
    ll cnt = get_count(mid,a);
    if (cnt>=m) ok = mid;
    else ng = mid;
}
```

ok という変数に$ M $番目に来る数$ K $が入っている。
これで$ A_x+A_y $を降順に並べた際、$ M $番目に来る数を求めることができた。

__2. $ K \leqq A_x+A_y $となる数の総和を求める__

$ getSum(K) := K \leqq A_x+A_y $となる数の総和、という関数を考えてみる（はまやんさんリスペクトその2）。
やっぱりここでも$ K-A_x \leqq A_y $と置く。$ A_x $を1つ固定すると、$ K \leqq A_x+A_y $にするためには$ K-A_x$以上の$ A_y $全てを$ A_x $と足し合わせていけばいい。
で、やっぱりAを昇順ソートしておくとlower_boundと累積和（$ A_y$ を全て足していると間に合わないので）で求められる。詳細な雰囲気は以下のコードで察してほしい。

```cpp

// s := Aの総和
// sum := Aの累積和
ll get_sum(ll K, ll s, const vector<ll> &a, const vector<ll> &sum) {
    ll ret = 0;
    int n = a.size();
    rep(i,n) {
        // K-Axをbと置く
        ll b = K-a[i];
        auto itr = lower_bound(a.begin(), a.end(), b);
        // lower_boundで得られたイテレータで始点のイテレータを引くと
        // AyがK-Ax以下となるインデックスがわかるので
        ll idx = itr-a.begin();
        // Aの総和からそこまでの累積和を引くと
        // K-Ax以上のAyの総和が分かる
        ret += (s-sum[idx]);
        // cnt := 足したAyの個数 
        ll cnt = n-idx;
        // Axをその分増やす
        ret += (a[i] * cnt);
    }
    return ret;
}
```

これでできた。

**3. 足しすぎた分の調整**

最初のサンプルはここまでやってきたコードで通すことが出来る。
しかし最初のサンプル

5 3
10 14 19 34 33

を

5 <b>2</b>
10 14 19 34 33

にしても同じ答えが出てしまう。
ここで$ \sum_{x=1}^{n} \sum_{y=1}^{n} A_x+A_y $ とし、全ての組み合わせにおいて$ A_x+A_y $を降順に並べたものを見てみると
{68, 67, 67, 66, 53, 53, 52, 52, .... } となっているのがわかる。
上から3つ目も2つ目も67になってしまっているため、$ M=3 $の答えが$ M=2 $の時にも出てしまうのである。
だから、この分を引いてやればいい。
$ getCount(K) $で同じ数になっている中では1番右の数（1番インデックスが大きい数）が得られるので、そこから$ M $を引いた個数分Kを引いてやる。

```cpp
ll K = ok;
ll ans = get_sum(K,s,a,sum);
ans -= (get_count(K,a)-m)*K;
```

これで全部通る。
ACコードは[これ](https://atcoder.jp/contests/abc149/submissions/9352502)