AGC 012 - A: AtCoder Group Contest

問題

A: AtCoder Group Contest - AtCoder Grand Contest 012 | AtCoder

解答

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

int main() {
  int N; cin >> N;
  vector<int> vs;
  rep(i, 3 * N) {
    int a; cin >> a;
    vs.push_back(a);
  }

  sort(vs.begin(), vs.end());

  ll ans = 0;
  for (int i = 0; i < 2 * N; i++) {
    if (i % 2 == 1) {
      ans += vs[3 * N - 1 - i];
    }
  }

  cout << ans << "\n";
  
  return 0;
}