kmjp's blog

競技プログラミング参加記です

TopCoder SRM 657 Div1 Easy ProblemSets、Div2 Medium ProblemSetsEasy

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で三分探索の話をしていたのですんなり解けた。