TopCoder SRM 613 Div1 Easy TaroFriends

SRM612に参加。Easyは解いたものの問題文誤読でちょっと時間がかかったためレート微減。
Mediumは通ったと思ったけどダメでした。
http://community.topcoder.com/stat?c=problem_statement&pm=13005

問題

N匹の猫が一次元の数直線上におり、座標C[i]が与えられる。
猫は一定時間後X大きいまたは小さい座標のいずれかに移動する。
この時、猫のいる一番小さい座標と大きい座標の差の最小値を答えよ。

解法

色々な手法がある。
自分はC[i]+XおよびC[i]-Xを列挙し、そこを左端になった場合を仮定して、猫をそこより右側のうちでできるだけ左に配置させ、差の値を求めた。

他のやり方としては、C[i]をソートし、左側何匹の猫は右に、残りは左に移動させて差を求める方法がある。

class TaroFriends {
	int N;
	public:
	int getNumber(vector <int> CC, int X) {
		int i;
		vector<ll> C;
		N=CC.size();
		FOR(i,N) C.push_back(CC[i]);
		
		sort(C.begin(),C.end());
		set<int> S;
		FOR(i,N) S.insert(C[i]-X);
		FOR(i,N) S.insert(C[i]+X);
		
		ll ret=1LL<<40;
		ITR(it,S) {
			ll ma=0;
			int ng=0;
			FOR(i,N) {
				if(C[i]-X>=*it) ma=max(ma,C[i]-X-*it);
				else if(C[i]+X>=*it) ma=max(ma,C[i]+X-*it);
				else ng++;
			}
			if(ng==0) ret=min(ret,ma);
		}
		return (int)ret;
	}
};

まとめ

本番「複数の猫は同じ座標にいられない」とか勝手な仮定を立ててしまったせいで時間をロスした…。
なぜそんなことを思ってしまったのか。
いや、そっちの方が問題として面白いと思うのだけどね…。