E - Handshake ～二分探索・累積和・格子点～

図

9 14
1 3 5 110 24 21 34 5 3

の場合の図 (サンプル2)

Quiz

https://atcoder.jp/contests/abc149/tasks/abc149_e

AC

https://atcoder.jp/contests/abc149/submissions/9230235

解説

• editorialより複雑なことをしてしまった気がするが、解けたので共有
• 全組み合わせをplotした後、和が大きい方から取っていく処理は、グリッド上でx+y=aなる右下がりの直線上か、それより上にある点で数えられる
• パラメータ a を二分探索し、M点取れるa, M点取れないaの境界を探す
• その境界のaを使って数えた時、点数がMより大きくなった場合は削る
• （境界だけど）取りすぎちゃった例（M=5点取りたいのに6点取ってしまった）

3 5
1 2 3

答え 24

6+5+5+4+4+4 = 28
取りすぎちゃった4を1つ削って24

計算量

• 二分探索の中で二分探索をしているのでO(N (logN)²)
• 10⁵ x 16 x 16 = 25600000 = 2.5 x 10⁷
• ややギリギリで間に合う (100ms)

グラフ

https://www.desmos.com/calculator

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～