kmjp's blog

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

Codeforces #326 Div1 A. Duff and Weight Lifting

ABCをそこそこの時間で解いて赤復帰。
http://codeforces.com/contest/587/problem/A

問題

N個の重りがある。各重りの重さは2^W[i]である。
Duffは1回で複数の重りを持ち上げられるが、その重さの合計は2の累乗でなければならない。

全重りを1回ずつ持ち上げるには、最低なんか重りを持ち上げればよいか。

解法

同じ重さの重りが2個あるなら、倍の重さの重りが1個あると考えても同じである。
よって、重りの合計を2進数表記して1の数を数えればよい。

int N;
int W[1110101];
int ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, W[x]++;
	
	for(i=0;i<=1100000;i++) {
		W[i+1] += W[i]/2;
		if(W[i]%2) ret++;
	}
	
	cout<<ret<<endl;
}

まとめ

ちょっと迷ったけどわかってしまえば簡単。