yukicoder : No.190 Dry Wet Moist

★は189と同じですが、こちらの方が簡単でした。
http://yukicoder.me/problems/499

問題

2N個の整数A[i]がある。
これらを2個ずつペアにする。

それぞれ以下の数が最大となるような組み合わせを求め、その数を答えよ。

• ペアの数値の和が負になるペアの数
• ペアの数値の和が正になるペアの数
• ペアの数値の和が０になるペアの数

解法

ペアの数値の和が０になるケースについては、multiset等を用いてA[i]に対し-A[i]が存在すればペア成立と見なしてペアから除く、という処理を繰り返せばよい。

ペアの数値の和が正になるケースについては、multiset等を用いて、残された最大のA[i]に対しlower_boundまたは尺取法で-A[i]+1以上の最小値を探し、存在すればペア成立と見なしてペアから除く、という処理を繰り返せばよい。

ペアの数値の和が負になるケースは、A[i]全体を符号反転し、上記処理を行うとラクである。

以下はlower_boundなのでO(N*logN)でちょっと重い。
尺取法だとO(N)でもっと軽いはず。

int wet(multiset<int> M) {
	int num=0;
	while(M.size()) {
		int v=*M.rbegin();
		M.erase(M.find(v));
		auto it=M.lower_bound(-v+1);
		if(it!=M.end()) num++, M.erase(it);
	}
	return num;
}

int moist(multiset<int> M) {
	int num=0;
	while(M.size()) {
		int v=*M.begin();
		M.erase(M.begin());
		if(M.count(-v)) num++, M.erase(M.find(-v));
	}
	return num;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int N;
	multiset<int> M,M2;
	
	cin>>N;
	FOR(i,2*N) cin>>x, M.insert(x),M2.insert(-x);
	_P("%d %d %d\n",wet(M2),wet(M),moist(M));
}

まとめ

解いててdryとwetとmoistのどれが正・負・０か混乱した部分が一番難しかった。