SRM573 Div1 Easy - TeamContest

問題

大学に人が3n人いて、i人目の強さはa[i]である
これらの3n人から3人チームをn組作る
3人チームの強さは3人の強さの最大値と最小値の和で決まる
0〜2人目が一緒にチームを組むことはもう決まっている
他の3n-3人のチーム分けを工夫すると、このチームより強いチームは最大何組作れるか

1 <= n <= 16
1 <= a[i] <= 10^6

解法

貪欲
ややこしいから最初の3人のチームの強さをkとし、その3人は除外して、残った人数を3nとする

まだ組になっていない人のうち最も強い人をチームの最大値担当として1人選ぶ
この人の強さをxとする
次にk-xを超える最小の強さを持つ人を1人探し、居たらその人を最小値担当として選ぶ
この人の強さはyとする
y以上x以下の強さを持つ人がいれば、そのうち最も弱い人を選び、この3人をチームにする

↑この流れを繰り返すのが最善

class TeamContest {
public:
	int worstRank(vector<int> a) {
		int k = max(a[0],max(a[1],a[2])) + min(a[0],min(a[1],a[2]));
		rep(i,3) a.erase(a.begin());
		sort(a.rbegin(), a.rend());
		int n = a.size(), res = 1, r = n-1;
		rep(l,n) {
			while (r>=0 && a[l]+a[r]<=k) r--;
			if (l+2<=r) res++, r -= 2;
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12470&rd=15493