ABC149 E - Handshake - あっとのTECH LOG

問題原文

問題要旨

$N$ 人のゲストがいる。 $i$ 番目のゲストの幸せパワーは $A_i$ である。
これらのゲストからある人の右手とある人の左手を選んで握手させるという操作を $M$ 回行う。ゲスト $i$ とゲスト $j$ が握手した時、全体の幸せ度は $A_i + A_j$ 増える。（最初、全体の幸せ度は0）
最大で全体の幸せ度をいくつにできるか？ただし、同じ握手は２回行えない。（異なる２人の右手左手を入れ替えて２回ペアにすることはできるが、１人の両手を握手させる操作を２回行うことはできない）

$1 \leq N \leq 10^{5}$
$1 \leq M \leq N^{2}$
$1 \leq A_i \leq 10^{5}$

解法

とりあえず入力はソートしておく。
当然全部のパターンは列挙できないので、ある基準を設けて、それより上の幸せ度を生むペアは全て採用する、と考える。
これを発展させると、『ギリギリ $M$ ペア作れるようなある基準（これを以後 $X$ とする）を設けたい』 気持ちになれる。そしてこれは二分探索で求められる。

$X$ が求められれば同じく二分探索を使って、ある $A_i$ について、 $X$ を超えるような相方を全て採用していく。ただし毎回相方をなめていては間に合わないので、累積和を用いてペアになって $X$ を超えるようなものの相方の幸せパワーを高速に求める。

最後に、 $X$ になるようなペアが複数個あって $M$ を超えている場合があるので、たしすぎた分を引く。（ここで引く値は $X$ で問題ない。なぜなら $X$ はギリギリ $M$ ペア作れるような基準値であるため）

実装

にぶたんは $M$ 個以上が確定した段階で枝刈りする
累積和は後ろからとっている。余計なものを足さないように便宜上先頭に０を追加している。これは好み（僕はすき）

from bisect import bisect_left
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

# にぶたん: Ai + Aj が X以上となるようなものがM通り以上あるか？
ok, ng = 0, 2 * 10 ** 5 + 1
while abs(ok - ng) > 1:
    X = (ok + ng) // 2
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, X - a)
        if cnt >= M:
            ok = X
            break
    else:
        ng = X

# 規定値以上のものを全てとる（ギリギリK個を超える）
ans = 0
cnt = 0
A_acc = [0] + list(accumulate(A[::-1]))[::-1]

for a in A:
    i = N - bisect_left(A, ok - a)
    cnt += i
    ans += a * i + A_acc[-i]

# 取りすぎた分を削る
ans -= max(0, cnt - M) * ok
print(ans)

感想

すごい苦手意識があったんですが、上位互換問の D - Pairs が登場したことで相対的に苦手意識がなくなり、よくみたら解けました。
ある基準をおいたらどうなる？どんな嬉しいことがある？ って考えるのはすごい大事な目線だと思いました。
勉強になった！！！