SRM657は不参加。
Easy早解き出来そうだったし、Medium解いた人少ないし参加してたらレート上がってたかもな。
http://community.topcoder.com/stat?c=problem_statement&pm=13771
http://community.topcoder.com/stat?c=problem_statement&pm=13772
問題
SRMはEasy/Medium/Hardの問題が1問ずつそろうと1回開催できる。
手持ちの問題ストックは以下の数だけある。
- Easyに使える問題がE個
- EasyまたはMediumに使える問題がEM個
- Mediumに使える問題がM個
- MediumまたはHardに使える問題がMH個
- Hardに使える問題がH個
最大でSRMを何回開催できるか。
Div2 Mediumは各値の上限が10^6、Div1 Easyでは10^18である。
解法
SRMの開催回数xに対し、開催可能かは以下のように判定できる。
- x回分のEasyをそろえるため、まずはE個分の問題から使う。足りない分はEM個から使う。
- x回分のHardをそろえるため、まずはH個分の問題から使う。足りない分はMH個から使う。
- 最後にx回分のMediumをそろえるためEM個・MH個の残り及びM個から使う。
それぞれEasy/Medium/Hardが揃え切れたら開催可能である。
開催可能判定は上記のとおりO(1)で容易にできる。
後はxを二分探索するだけ。
Div2 Mediumの制限なら総当たりでも良い。
class ProblemSets { public: bool ok(ll tar,ll E, ll EM, ll M, ll MH, ll H) { if(tar>E) EM -= tar-E; if(tar>H) MH -= tar-H; if(EM<0) return false; if(MH<0) return false; if(EM+M+MH<tar) return false; return true; } long long maxSets(long long E, long long EM, long long M, long long MH, long long H) { ll tar=0; int i; for(i=60;i>=0;i--) if(ok(tar+(1LL<<i),E,EM,M,MH,H)) tar += 1LL<<i; return tar; } }
まとめ
直前にyukicoderで三分探索の話をしていたのですんなり解けた。