ABC149 E - Handshake - ツバサの備忘録

解法

明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。
ある得点 $X$ が達成できるとすると、明らかに $X$ 未満の任意の得点 $Y$ は、全く同じ手を選ぶことで達成でき、達成できないときは $X$ 以上の得点はどう頑張っても達成できないので、

$X$ 以上の得点を達成できるか

について単調性が存在します。
この $X$ について二分探索をしたいのですが、うまくいきません(僕はいきませんでした)。ので、少し見方を変えます。
得点の和が高いペアから順番に握手をしていくのが最適だったので、ある得点 $P$ について、

$P$ 以上となるペアについては握手を行い、 $P$ 未満となるペアについては握手をしない

という区切り目が存在するはずです。
$P$ 以上となるペアの個数が $M$ 個以上になると、 $M$ 回握手することができます。
$P$ 以上となるペアの個数についても、 $P$ が減少すれば個数が増加し、単調性が存在しています。ので、

$P$ 以上となるペアの個数が $M$ 以上になる

ような、最大の $P$ を二分探索で求めることができます。
すると、その $P$ 以上のペアの総和を求めればよいです。
片手が $A_{i}$ のとき、もう片方の手は、 $(P-A_{i})$ 以上の $A_{j}$ を選ぶことができます。この $A_{j}$ の個数は、 $A$ が降順ソートされていれば、二分探索で求めることができます。
これにより、ペアの個数を求めることができました。
総和についてもほぼ同様で、 $A_{1}$ から $A_{j}$ までの総和と、 $A_{i}\times(選べるA_{j}の個数)$ の総和を全ての $i$ について足したものになります。
これは、後者についてはそのまま個数をかければよく、前者については累積和をあらかじめ計算しておくことで、高速に計算することができます。
あとは、コーナーケースである、

$P$ 以上となるペアの個数がぴったり $M$ ではなかった場合

についての差分を計算すればよいです(サンプル2参照)。
得点の和が $P+1$ 以上となるペアは $M$ 個未満になってしまうはずなので、今 $P$ 以上となるペアの個数が $M+q$ 個あるとしたときに、総和から除くべき $q$ 個のペアは、得点が $P$ となっているものについてです。
ということで、 $Pq$ を、全体の総和から引いてあげれば求める答えとなります。

感想

見るからに二分探索をしたいなぁ、と思っていたのですが、うまく二分探索をする方法を考えるのに詰まってしまいました。
見方の変え方が課題です。