TopCoder SRM 750 Div1 Easy Div2 Hard IdenticalBags

何気に通常SRMで全完は初かも。
https://community.topcoder.com/stat?c=problem_statement&pm=15305

問題

N種類のキャンディがあり、i番目の種類のキャンディはC[i]個ある。
これらをいくつかの袋に詰めたい。

この時、各袋の中身は同じで、かつB個ずつキャンディが入っているようにしたい。
最大で同じ袋を何通り作れるか。

解法

袋の数が決まれば、各袋に各種類何個までキャンディを入れられるか判定でき、総和がB個を超えるか判定できる。
よって袋の数を二分探索しよう。
処理手順によって、途中64bit値をオーバーフローする可能性があるので注意すること。

class IdenticalBags {
	public:
	
	long long makeBags(vector<long long> C, long long B) {
		
		ll ret=0;
		for(int i=59;i>=0;i--) {
			__int128_t num=0;
			FORR(c,C) num+=c/(ret+(1LL<<i));
			if(num>=B) ret+=1LL<<i;
		}
		return ret;
		
	}
}

まとめ

２回連続二分探索か…。