Easyはさっくり解けたけど、Medium解けなかったしunratedになってなかったらレート微減してそう。
https://community.topcoder.com/stat?c=problem_statement&pm=14104
問題
あるロボットを作るには1~mの部品が1つずつ必要である。
これらの部品をn個の店で集めよう。
各店では、A[i]~B[i]の範囲の部品を計K[i]個まで買える。
店で最適な部品の買い方をするとき、最大何台のロボットを作れるか。
解法
2分探索で解く。
2分探索で作るロボット台数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とか使ってちょっと計算量心配だったけど、普通に通った。