Codeforces #184 Div2. C. Ivan and Powers of Two

CF#184はDiv2 Onlyなので練習のみ。
http://codeforces.com/contest/305/problem/C

問題

N要素の数列Aに対し、が与えられる。
ここに、２の累乗の数をいくつか足し、全体の和をの形としたい。
足すべき最少の２の累乗数の数を答えよ。

解法

和の２進数表記において、A[i]に対しA[i-1]-1の桁まではすでに1が埋まっていたとすると、(A[i-1])～(A[i]-1)桁のうち1でない数だけ２の累乗数を加算しなければならない。
あとはA[i]桁以上の値だけを覚えておいて処理すればよい。

int N;
ll A[1000001];

void solve() {
	int f,r,i,j,k,l, x,y,ma,nt;
	ll res=0,num=0,digit=0;
	
	N=GETi();
	FOR(i,N) A[i]=GETi();
	
	j=0;
	while(j<N || num) {
		while(j<N && digit==A[j]) {
			num++;
			j++;
		}
		if(j<N && num==0) {
			res += A[j]-digit;
			digit=A[j];
		}
		else {
			digit++;
			res += 1-(num&1);
			num>>=1;
		}
	}
	cout << res << endl;
	return;
}

まとめ

ちょっとややこしいけど面白い問題。