Croc Champ 2013 - Final : C. Memory for Arrays

４か月前に解いた問題をここで書こうとすると、解法を忘れて戸惑う…。
CFはブログに書いてない問題がたまってきてしまった。

これは自力で解けた問題。
http://codeforces.com/contest/309/problem/C

問題

サイズがA[i]のN個のメモリ領域が与えられる。
そこに2の累乗のサイズであるB[i]個のデータを格納していきたい。
データを最大何個メモリ領域に格納できるか答えよ。

解法

データのサイズは２の累乗なので、A[i]のメモリ領域は結局２の累乗サイズのメモリ領域の和と考えることができる。
そのようにして、各２の累乗ごとのサイズのメモリ領域が何個あるか数える。

答えるのはデータの個数なので、小さなデータから格納していけばよい。
サイズが2^iのデータがあったら、それを2^i、2^(i+1)、…と小さい順にメモリ領域に入るか試みていく。
仮にj>iである2^jのメモリ領域に2^iのデータを入れたら、2^i、2^(i+1)、…、2^(j-1)の新たな空き領域ができる。

int N,M;
ll A[40],B[40],C[40];

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	cin>>N>>M;
	FOR(i,N){
		j=GETi();
		FOR(k,31) A[k]+=(j>>k)&1;
	}
	FOR(i,M) B[GETi()]++;
	
	ll res=0;
	FOR(i,31) {
		for(j=i;j<31;j++) {
			if(!B[i]) break;
			
			ll c=min(B[i],A[j]<<(j-i));
			res+=c;
			B[i]-=c;
			A[j]-=c>>(j-i);
			c-=(c>>(j-i))<<(j-i);
			if(c) {
				A[j]--;
				c=(1<<(j-i))-c;
				k=i;
				while(c) {
					if(c&1) A[k]++;
					c>>=1;
					k++;
				}
			}
		}
	}
	
	_P("%d\n",res);
	
	return;
}

まとめ

LinuxのBuddyアロケータを思い出す。