TopCoder SRM 561 Div1 Easy ICPCBalloons

今回はMediumが解けずEasyを解いて少しランク上昇。
前回が簡単すぎたためか、今回はEasyでもちょっとややこしい。
この問題はDiv2ではMediumだったけど、そちらの正答率もかなり低いね。
http://community.topcoder.com/stat?c=problem_statement&pm=12314

色んな色の風船があり、各色の風船の数が与えられる。
また、各色の風船はいずれも同じ大きさで、中サイズか大サイズかのいずれかである。
それとは別に、複数のプレイヤーが必要とする風船の数が与えられる。

問題は、各プレイヤーに必要な数の同色の風船を与える場合、既存の風船で不足するならば色を塗り替えて数を満たすようにする際、塗り替える風船の数を最小化するもの。

まず、この問題は風船のサイズが２種類あるので、サイズを跨ぐ塗り替えはできない。
この問題は、プレイヤー数が高々13なので、各プレイヤーが中・大両サイズを取るケースを2^13通り試せばよい。

各ケースでは、まずプレイヤーを要求数で降順に並べ、各サイズの風船も数で降順に並べる。
各サイズの合計数がプレイヤーの要求数の合計に足りない場合は不可。
そうでない場合、プレイヤーの要求数と風船数を比較して、風船が足りなければ足りない分を塗り替え色として累積すればよい。

class ICPCBalloons {
	int med[51];
	int N,A;
	int NMB,NLB;
	vector <int> mb;
	vector <int> lb;
	vector <int> MA;
	public:
	int calc(int mask) {
		int nm,nl,nmb,nlb;
		int i;
		
		nm=nl=nmb=nlb=0;
		FOR(i,A) {
			if(mask & (1<<i)){
				nm++;
				nmb += MA[i];
			}
			else {
				nl++;
				nlb += MA[i];
			}
		}
		if(nmb > NMB) return -1;
		if(nlb > NLB) return -1;
		
		//MB;
		int c=0;
		int ret=0;
		
		FOR(i,A) {
			if((mask & (1<<i))==0) continue;
			if(MA[i] > mb[c]) ret+=MA[i]-mb[c];
			c++;
		}
		
		c=0;
		
		FOR(i,A) {
			if((mask & (1<<i))!=0) continue;
			if(MA[i] > lb[c]) ret+=MA[i]-lb[c];
			c++;
		}
		return ret;
		
		
	}
	
	int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted) {
		int i,j,mask;
		N=balloonCount.size();
		mb.clear();
		lb.clear();
		A=maxAccepted.size();
		NMB=NLB=0;
		FOR(i,N) {
			if(balloonSize[i]=='M'){
				mb.push_back(balloonCount[i]);
				NMB+=balloonCount[i];
			}
			else {
				lb.push_back(balloonCount[i]);
				NLB+=balloonCount[i];
			}
		}
		FOR(i,A) {
			mb.push_back(0);
			lb.push_back(0);
		}
		
		
		sort(mb.begin(),mb.end());
		reverse(mb.begin(),mb.end());
		sort(lb.begin(),lb.end());
		reverse(lb.begin(),lb.end());
		sort(maxAccepted.begin(),maxAccepted.end());
		reverse(maxAccepted.begin(),maxAccepted.end());
		MA=maxAccepted;
		int res = -1;
		
		FOR(mask,1<<A) {
			int r = calc(mask);
			if(res==-1 || (r>=0 && r<res)) res = r;
		}
		return res;
		
	}

};

まとめ

今回は問題文が長くて意図を読み取るのに苦戦した。
Easy位だと正答率高いし、問題読み取りで時間を食うのが苦しいなぁ。