TopCoderOpen 2016 Round1A Medium EllysScrabble

不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=14188

問題

N要素の数列集合S[i]がある。
ここから、要素対をP個選んだ時、各要素対の差の最大値が最小値になるようにしたい。
その場合の要素対の差の最大値を求めよ。

解法

まずSをソートする。
後は二分探索で許容する要素対の差の最大値を探そう。

要素対の差の最大値が定まったら、Sを小さい順に見て貪欲にその最大値以下の差である2要素を対として選べばよい。

class EllysSocks {
	public:
	int getDifference(vector <int> S, int P) {
		int i,j;
		sort(S.begin(),S.end());
		vector<int> D;
		FOR(i,S.size()-1) D.push_back(S[i+1]-S[i]);
		
		int mi=(1<<30)-1;
		for(i=29;i>=0;i--) {
			int tmp=mi-(1<<i);
			int num=0;
			FOR(j,D.size()) if(D[j]<=tmp) num++, j++;
			if(num>=P) mi=tmp;
		}
		return mi;
		
	}
}

まとめ

やっぱりTCO Round1はDiv2位の難易度？