TopCoder SRM 598 Div1 Easy BinPacking

SRM598は昼間回なので不参加。
Mediumを１発ACできなかったので出なくてよかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12861

問題

N個の荷物の重さW[i]が与えらえる。それぞれの重さは100～300である。
これら全ての荷物を300の重さまで耐えられる容器に詰め込む場合、最少何個容器があればよいか。

解法

重さが100の荷物は３つ容器に詰め込めるが、それ以外は２個が限界である。
よって、まだ容器に詰めていない荷物を重い順に選択し、一緒に容器に入れられるほかの荷物があれば、ペアにして重い順に容器に詰めていく。
一緒に入れられるものがなければ１個ずつ詰めていく。
もし上記手順で残りが重さ100の荷物だけになったら、それらを3つずつ詰めればよい。

なお、Div2 Mediumでは重さが101～300のため、同様のコードを流用できるが100の荷物を３つ詰め込むケースは存在しない。

class BinPacking {
	public:
	int minBins(vector <int> item) {
		int N=item.size();
		int r=0,i;
		sort(item.begin(),item.end());
		for(int x=N-1;x>=0;x--) {
			if(item[x]>=999) continue;
			if(item[x]==100) {
				int j=0;
				FOR(i,N) if(item[i]==100) j++;
				return r+(j+2)/3;
			}
			
			for(int y=x-1;y>=0;y--) {
				if(item[x]+item[y]<=300) {
					item[y]=999;
					break;
				}
			}
			item[x]=999;
			r++;
		}
		return r;
	}
};

まとめ

Div1 EasyとDiv2 Medium、こういう条件の分け方は珍しいな。