AGC 012 - A: AtCoder Group Contest

問題

agc012.contest.atcoder.jp

解答

チームの強さに影響する人として最も採用したい人は a_iが最大の人物だが、 この人は最強のため、3人チームでは必ず1番強くなってしまうためチームの強さに影響しない。  a_iが最大の人物を入れたチームには、のこる人物のうち最大の a_iを持つ人物、つまり元の集合で2番目に強い人をチームの強さに影響する人物として採用できる。よって2番目に a_iが高い人が真っ先に採用される。 同様にチーム内最強と2番手をソート降順に順々に抜擢していけば、チームの強さの和を最大化出来る。 各チームで最弱の人の入れ方は、残ったスペースに適当に詰めると考えることにして考慮から外しておいてよい。