Codeforces #165 Div1. A. Magical Boxes

#165に参加。Aを最初10分で解けたと思ったら最後までバグが取れなかった…。
なんとかBだけ解いたけど微妙な順位でまさかのDiv2落ち。
ひどい結果だ…。

http://codeforces.com/contest/269/problem/A

サイズ2^(k-1)の箱は2^kに4つ収まる。
色んな数とサイズ(２の累乗のみ）の箱が与えられたとき、それらを１つで全部含める最少の箱の数を答える問題。

注意点として、全部で１個しか箱がない場合でも、それを含む箱はそれより大きくないといけないこと。
これに気づかなくてこれ落とした…。

以下のコードは、箱をサイズ順にソートし、「小さい箱をこの箱に換算すると何個分か」ということを計算していってる。
でももっと速く解いてる人は「一番大きな箱で何個分か」を計算してるね。

int N;
vector<pair<ll, ll> > box;

void solve() {
	int f,r,i,j,k,l;
	int x,y;
	
	N=GETi();
	FOR(i,N) {
		j=GETi();
		k=GETi();
		box.push_back(make_pair(j,k));
	}
	sort(box.begin(),box.end());
	
	ll cs=box[N-1].first;
	ll ct=box[N-1].second;
	FOR(i,N-1) {
		if(cs-box[i].first>15) continue;
		ll tt = cs-box[i].first;
		ll ct2 = box[i].second >> (2*tt);
		if(box[i].second % (1LL<<(2*tt))) ct2++;
		ct = max(ct,ct2);
	}
	
	ct=(ct+3)/4;
	cs++;
	while(ct>1) {
		ct=(ct+3)/4;
		cs++;
	}
	_P("%lld\n",cs);
	
	return;
}

まとめ

今回はこの問題で時間を取りすぎて他にほとんど回せなかった。
確かに同じサイズの箱に入れられるとは書いてないね…。
バグ取れないときはさっさとあきらめる癖をつけないとダメだ。