TopCoder SRM 649 Div1 Hard CartInSupermarket

本番Easy/Mediumでたっぷり時間があったのに間にあわず残念。
http://community.topcoder.com/stat?c=problem_statement&pm=13370

問題

初期状態でN列のカート列があり、各列はA[i]個のカートからなる。
１ターン毎に、カート列群に対しそれぞれ以下の何れかの行動をどちらか１つ行える。

列のカートを１つ減らす
列を２つに分割する（分割後の２列のカート数配分は任意）

ただし、列の分割は全体で最大B回までしか行えない。
全てのカートを取り除くのにかかる最小ターン数を答えよ。

解法

最小ターン数Tを二分探索する。

Tを仮置きしたら、各N個のカート列に対し、Tターン内でA[i]個の列を取り除くのに必要な最小分割数を求めて、その分割数の和がB以下かどうか判定する。

最小分割数についても再度二分探索の要領で求める。

TopCoder SRM 649 Div2 Medium CartInSupermarketEasy - kmjp's blog
上記Div2 Mediumの考察によると、A[i]個のカートを(X-1)回分割し、X列にしながら取り除く場合、 $Y=\lceil \log_2 X \rceil$ となるYに対を用いて必要ターン数は $Y + 1 + \lceil \frac{A_i - 2^Y}{X} \rceil$ となる。

この式を変形すると $X \le \frac{A-2^Y}{T - (Y+1)}$ となる。
この式と $2^{Y-1} \lt X \le 2^Y$ を満たすXがあれば、それがTターン以内を満たす最小のXである。
各Yに対し上記Xのチェックをすればよい。

class CartInSupermarket {
	public:
	
	ll numdiv(ll L,ll T) {
		if(L<=T) return 1;
		for(int i=1;i<=29;i++) {
			if(1LL<<i > L) break;
			if(T<=i+1) break;
			ll a=(L-(1<<i));
			ll b=T-(i+1);
			ll N=(a+b-1)/b;
			if(N>(1<<(i-1)) && N<=1<<i) return N;
		}
		return 1LL<<30;
	}
	
	ll tdiv(int v,vector <int> a) {
		ll tot=0;
		ITR(it,a) tot += numdiv(*it,v)-1;
		return tot;
	}
	
	int calcmin(vector <int> a, int b) {
		sort(a.begin(),a.end());
		ll ret=(1LL<<30)-1,i;
		for(i=29;i>=0;i--) if(tdiv(ret-(1<<i),a)<=b) ret -= 1<<i;
		return ret;
	}
}

まとめ

本番はDiv2 Mediumもないので $Y + 1 + \lceil \frac{A_i - 2^Y}{X} \rceil$ の考察に自信が持てないこともあり時間切れ。