AtCoderログ：0061 - AGC 012 A

問題

問題文

AtCoder Group Contestの参加者に $3N$ 人が参加します。$i$ 番目の参加者の 強さ は整数 $a_i$ で表されます。参加者が $3$ 人 $1$ 組となるようにチームを $N$ 組作ることにしました。$1$ 人の参加者が複数のチームに所属することはできません。
チームの強さはチームメンバーの強さのうち $2$ 番目に大きい値で表されます。 例えば、強さが $1,5,2$ のメンバーからなるチームの強さは
$2$ になり、強さが $3,2,3$ のメンバーからなるチームの強さは
$3$ になります。
$N$ 組のチームの強さの和としてありうる値のうち、最大の値を求めてください。

制約

・$1 \le N \le 10^5$
・$1 \le a_i \le 10^9$
・$a_i$ は整数

収録されている問題セット

• AtCoder に登録したら次にやること (第06問類題)

回答

回答1 (AC)

最もシンプルなアプローチは全探索です。しかし、最初のチームは $3N$ 人から $3$ 人を選ぶので $O(N^3)$ 通りの場合があり、これだけでTLEになっていまいます。そこで全探索しない方法が必要です。

$3N$ 人の参加者を強い順にソートし、強い方から $N$ 人を $\square$、次の $N$ 人を $\circ$、最後の $N$ 人を $\triangle$ で表すことにします。今、$i$ 番目のチームに $\triangle$ が2人いる、つまり $(＊, \triangle, \triangle)$ になったとしましょう。ここでチーム内の表記は強い順とし、＊ は $\square, \circ, \triangle$ のいずれかを表します。$\triangle$ は全部で $N$ 人なので、どこかに $\triangle$ が含まれないチームがいるはずで、それを $j$ 番目のチームとします。$j$ 番目のチームの $3$ 人目が $\circ$ であったとすると、$i$ 番目の $2$ 人目と $j$ 番目のチームの $3$ 人目を入れ替えることで、$i$ 番目のチームの強さは $\triangle$ から $\circ$ に上昇するので、入れ替えた方がチームの強さの総和は大きくなります。$j$ 番目のチームの $3$ 人目が $\square$ の場合も同様です。このような操作を繰り返すことにより、チームの強さの総和を最大にするには、全てのチームの $3$ 人目は $\trianble$ になっている必要があることがわかります。

$N$ チームの $1$ 人目と $2$ 人目を全探索しようとしてもまだ計算量が大きいので、さらなる工夫が必要です。$\circ$ の中で強い順に $\circ(1)$ $, \circ(2),\dots,\circ(N-1),\circ(N)$ とかきます (丸囲み数字と思ってください)。$i$ 番目のチームに $\circ(N-1)$ が、$j$ 番目のチームに $\circ(N)$ が所属しているとすると、$\circ(N-1)$ と $\circ(N)$ はどちらも $2$ 人目になっているはずです。そこで $i$ 番目のチームの $2$ 人目 (つまり $\circ{(N-1)}$ と $j$ 番目のチームの $1$ 人目を入れ替えると、$i$ 番目のチームの $2$ 人目は＊となるので、チームの強さの総和は増大します。つまり $\circ{(N-1)}$ と $\circ{(N)}$ は同じチームに所属した方が良いのです。

同様に考えることで、$\circ{(N-3)}$ と $\circ{(N-2)}$ は同じチーム、...、$\square(1)$ と $\square(2)$ は同じチームに所属するのが良くて、チームの強さの総和が最大になるのは以下のような場合であることがわかります。このとき、チームの強さの総和は「$2$ 人目の強さ+$4$ 人目の強さ+...+ $2N$ 人目の強さ」となります。

上記の考察により、チームの強さの総和になる場合が特定できました。コードの処理としては、$3N$ 人のメンバーの強さを配列 a() で受け取り、強い順 (降順) にソートし、1 人目, 3 人目, ..., 2n-1 人目の強さの合計を出力すれば良いでしょう。コードではインデックスが 0 から始まるため、上記の考察とインデックスがずれていることに注意してください。コードは以下のようになりました。

agc012a-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  vector<int> a( 3*n, 0 );
  for ( int i=0; i<3*n; i++ ) {
    cin >> a.at(i);
  }
 
  sort( a.rbegin(), a.rend() );
  
  int64_t sum = 0;
  for ( int i=0; i<n; i++ ) {
    sum += a.at(2*i+1);
  }
 
  cout << sum << endl;
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0060 - ABC 156 C