No Caffeine, No Life

プログラミング(主にPython)

ABC 062 D:3N Numbers

問題:

D: 3N Numbers - AtCoder Beginner Contest 062 | AtCoder

解説:

詳しい考え方は、atcoderの解説を参照。その解説通りに組んでみたのが解答例。

個人的には、ポイントは

  • 前半から{\displaystyle k }個({\displaystyle  N \leq k \leq 2N})の選んだ中で、大きい順に{\displaystyle N }個の和を計算(もしくは小さい順に{\displaystyle N }個の和を計算)

というところ。ここで、「要素を足して、足された配列から小さいものを取り出す」heappushpopが役立つ。

解答例: