AGC 012 - A: AtCoder Group Contest

問題

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

解答

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

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;
}