TopCoder SRM 681 Div1 Easy FleetFunding

Easyはさっくり解けたけど、Medium解けなかったしunratedになってなかったらレート微減してそう。
https://community.topcoder.com/stat?c=problem_statement&pm=14104

問題

あるロボットを作るには1～mの部品が1つずつ必要である。
これらの部品をn個の店で集めよう。
各店では、A[i]～B[i]の範囲の部品を計K[i]個まで買える。

店で最適な部品の買い方をするとき、最大何台のロボットを作れるか。

解法

２分探索で解く。
２分探索で作るロボット台数Rを仮決めしよう。

すると各部品をR個ずつ買うことになる。
部品1から順に見ていって、その部品を買える店のうち、B[i]の小さい店から優先して部品を買おう。
この手法だと1回の判定がO(nm)程度かかるので二分探索込みでO(nm*log(n*max(k)))位かな。

R個ずつ部品を揃えられるかの判定は、条件をグラフにすることで最大フロー問題として解くこともでき、その場合辺がO(n^2)程度のグラフを作れる。

vector<pair<int,int> > V[101010];

class FleetFunding {
	public:
	
	int ok(int v,int m) {
		map<int,int> M;
		int i;
		
		for(i=1;i<=m;i++) {
			while(M.size() && M.begin()->first<i) M.erase(M.begin());
			FORR(r,V[i]) M[r.first]+=r.second;
			int d=v;
			while(d>0) {
				if(M.empty()) return 0;
				int s=min(d,M.begin()->second);
				d-=s;
				M.begin()->second-=s;
				if(M.begin()->second==0) M.erase(M.begin());
			}
		}
		return 1;
	}
	
	int maxShips(int m, vector <int> k, vector <int> a, vector <int> b) {
		int i;
		int N=k.size();
		FOR(i,m+2) V[i].clear();
		FOR(i,N) V[a[i]].push_back({b[i],k[i]});
		
		int ret=0;
		for(i=29;i>=0;i--) if(ok(ret+(1<<i),m)) ret+=1<<i;
		return ret;
	}
}

まとめ

mapとか使ってちょっと計算量心配だったけど、普通に通った。