TopCoder SRM 608 Div1 Easy MysticAndCandies

SRM608は不参加。復習したらEasyででこずったし、Mediumで1ミスしたし結果だけ見れば出なくてよかった回。
問題はDiv2 Mediumを難しくしたもので、300ptとなっている。
http://community.topcoder.com/stat?c=problem_statement&pm=12997

問題

N個の箱があり、それぞれに飴がlow[i]～high[i]の間のいずれかの個数入っている。
また、合計C個の飴が入っていることがわかっている。

N個の箱のうち幾つかの箱を選んだ時、合計で必ずX個以上の飴が入っているようにしたい。
最小何個の箱を選べば、必ずX個以上となるか。

解法

幾つかの箱を選んだとき、最悪ケースで手に入る飴の数は以下のように考えることができる。
各箱low[i]個の飴は必ず入っており、合計でC-sum(low)の分だけどこに入っているかわからない飴がある。
「どこに入っているかわからない飴」は最悪ケースで選ばなかった箱に入っており、その数はmax(C-sum(low), sum[i∈選択しない箱](high[i]-low[i]))である。
逆に手に入る飴の数は、sum[i∈選択した箱](low[i]) + *1 - max(C-sum(low), sum[i∈選択しない箱](high[i]-low[i])) となる。

よって、飴の数を多くするには、以下の２つのアプローチがある。

• lowが多いものを優先的に選択し、必ず手に入る量を増やす。
• highが多いものを優先的に選択し、highが小さいものが選択外となるようにすることで、選択しない箱に流れる飴を減らす。

それぞれlow/highで降順に並べ、先頭a個を選択して条件を満たす最小値を探せばよい。

class MysticAndCandies {
	public:
	int minBoxes(int C, int X, vector <int> low, vector <int> high) {
		vector<pair<int,int> > P;
		int i,j;
		int LT=0;
		int N=low.size(),mi=low.size();
		FOR(i,N) C-=low[i];
		
		FOR(i,N) P.push_back(make_pair(high[i],low[i]));
		
		sort(P.begin(),P.end());
		reverse(P.begin(),P.end());
		for(i=1;i<=N;i++) {
			int lt=0,dt=0;
			FOR(j,i) lt+=P[j].second;
			for(j=i;j<N;j++) dt+=P[j].first-P[j].second;
			dt=min(dt,C);
			if(lt+(C-dt)>=X) mi=min(mi,i);
		}
		
		FOR(i,N) P[i]=make_pair(low[i],high[i]);
		sort(P.begin(),P.end());
		reverse(P.begin(),P.end());
		for(i=1;i<=N;i++) {
			int lt=0,dt=0;
			FOR(j,i) lt+=P[j].first;
			for(j=i;j<N;j++) dt+=P[j].second-P[j].first;
			dt=min(dt,C);
			if(lt+(C-dt)>=X) mi=min(mi,i);
		}
		return mi;
		
		
	}
};

まとめ

low順で選ぶかhigh順で選ぶか迷ったけど、まさかのどっちもやる案でした。

*1:C-sum(low