kmjp's blog

競技プログラミング参加記です

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

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

問題

N要素の数列Aに対し、2^{A_0},2^{A_1}, ... 2^{A_{N-1}}が与えられる。
ここに、2の累乗の数をいくつか足し、全体の和を2^V-1の形としたい。
足すべき最少の2の累乗数の数を答えよ。

解法

和の2進数表記において、A[i]に対しA[i-1]-1の桁まではすでに1が埋まっていたとすると、(A[i-1])~(A[i]-1)桁のうち1でない数だけ2の累乗数を加算しなければならない。
あとは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;
}

まとめ

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

広告を非表示にする