AtCoder Group Contest [AtCoder Grand Contest 012 A]

atcoder.jp

チームの中央値をなるべく大きくすることを考えます。

中央値の個数は3人1組なので N 個です。
N 個の値（N人）を参加者 3N 人のうちのどこから選ぶか。

最初に考え付いたのは以下のような選び方です。A がチームの最小値、B がチームの中央値、C がチームの最大値と思ってください。

・A A A A A A / B B B B B B / C C C C C C

i 番目、i+n 番目、i+2n 番目をチームにする選び方です。一見良さそうに見えますが、この通りに書いて提出したところ WA でした。より優れた B の選び方があるみたいです。

結論を言ってしまえば、以下の選び方が答えになります。

・A A A A A A / B C B C B C / B C B C B C

なるほど～と思いました。B をなるべく右側に寄せる、という抽象的な思考が求められているんですね。

void solve () {

	int n = nextInt();
	int[] ar = nextIntArray(n*3);
	Arrays.sort(ar);

	long ans = 0;
	for (int i=n; i<n*3; i+=2) {
		ans += ar[i];
	}

	out.println(ans);

}