TopCoder SRM 603 Div2 Medium SplitIntoPairs

今回はDiv1 Easyとは別の問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12939

問題

2N個の整数A[i]と、負の数Xが渡される。
AをN個の２整数のペアに分類したとき、その積がXを超えるペアの数を最大化せよ。

解法

Xが負であるのがポイント。
２整数のペアがXを下回る可能性があるのは、正の値と負の値を掛けるときだけである。

よって、A中で負の数同士および正の数同士を絶対値の大きい順にペアにしていく。
残るのは1個以下の正の数と、1個以下の負の数と0である。
残されたペアの積がXを下回るのは正の数と負の数が１個ずつしか残っていない場合で、それ以外は0以上になるのでXを下回ることはない。

最後の掛け算で地味に32bitをあふれる可能性があるので注意。

class SplitIntoPairs {
	public:
	int makepairs(vector <int> A, int X) {
		int N=A.size()/2;
		int i;
		sort(A.begin(),A.end());
		FOR(i,100) {
			if(!A.empty() && A[1]<0) A.erase(A.begin()),A.erase(A.begin());
			if(!A.empty() && A[A.size()-2]>0) A.resize(A.size()-2);
		}
		if(A.size()==2) return N-(A[0]*(ll)A[1]<X);
		return N;
	}
};

まとめ

Xが負という縛りはなくてもいいんじゃないかと思ったけどどうなんだろう。