TopCoder SRM 582 Div1 Easy SpaceWarDiv1

この日はSRM582とCF188の連戦。
どちらも微妙な出来てレートは微増。下がらなかっただけマシだけど…。
SRM582は案の上600ptが解けず。Easyを少し手こずって解いたけどTZTesterのバグ？もあってsubmitが遅れた。
http://community.topcoder.com/stat?c=problem_statement&pm=12604

問題

N人の少女がいて、それぞれの強さが整数値で与えられる。
また、E種類の敵がいてそれぞれの強さと数が与えられる。

各少女は自分以下の強さの敵を倒すことができ、その際１匹倒すごとに１疲労がたまる。
敵全部を倒す際に、N人の少女の疲労の最大値を最小化し、その値を答える。

解法

最初は少女の強さを弱い順にソートして、弱い順から数を決定できないかなーとしばらく考えていた。
しかしその後二分探索でいいじゃん、と気づいて実装を変更。

各人が倒す敵の数==疲労の値がわかれば、その疲労の範囲で敵を全滅させるかどうかはO(N+E)でわかる。
あとは二分探索で疲労の値を求めるだけ。

class SpaceWarDiv1 {
	int M,E;
	vector<int> mg,es;
	vector<long long> ec;
	
	ll hoge[51];
	public:
	int okok(ll cur) {
		int i,j;
		vector<long long> e=ec;
		
		FOR(i,M) {
			ll le=cur;
			FOR(j,E) {
				if(es[j]<=mg[i]) {
					ll aa=min(le,e[j]);
					le-=aa;
					e[j]-=aa;
				}
			}
		}
		FOR(i,E) if(e[i]>0) return 0;
		return 1;
	}
	
	long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount) {
		
		M=magicalGirlStrength.size();
		sort(magicalGirlStrength.begin(),magicalGirlStrength.end());
		E=enemyStrength.size();
		
		mg=magicalGirlStrength;
		es=enemyStrength;
		ec=enemyCount;
		
		int i,j,x,y;
		FOR(i,E) if(enemyStrength[i]>magicalGirlStrength[M-1]) return -1;
		ZERO(hoge);
		FOR(x,M) {
			FOR(y,E) {
				if(magicalGirlStrength[x]>=enemyStrength[y]) {
					hoge[x]+=enemyCount[y];
					enemyCount[y]=0;
				}
			}
		}
		
		ll lo=0,hi=1LL<<60;
		FOR(i,65) {
			ll pi=(hi+lo)/2;
			if(okok(pi)) {
				hi=pi;
			}
			else {
				lo=pi+1;
			}
		}
		
		lo=max(lo-5,0LL);
		while(1) {
			if(okok(lo)) return lo;
			lo++;
		}
		
		return 0;
	}
	
};

まとめ

TZTesterがlong long型の定数をうまく扱ってくれず、テストを通すのに苦労した。
解けて良かったと言えばよかったけど、これは２分探索だともっと早く気づきたかったな。