TopCoder SRM 596 Div1 Easy IncrementAndDoubling

前回不参加なので久々のSRM。
Easyを爆速で解けたのだが、Mediumをまたしょうもないミスで落とした。
Medium解答者が多かったため、レートは微増にとどまった。
http://community.topcoder.com/stat?c=problem_statement&pm=12790

問題

N個の0からなる数列に、以下の処理を行うコストは1である。

• いずれかの要素を1増やす。
• 全部の要素を２倍にする。

最終的に必要な数列が与えられたとき、その数列を作るための最小コストを答えよ。

解法

１増やすより２倍する方が効率が良い。
よって、各数列要素については、２倍を繰り返しながら途中の桁が１になるタイミングで１増やせばよい。
２倍繰り返す回数は、最大値の最大桁数になるので、回答は(全要素のbit countの和)+(最大値の最大桁数)になる。

class IncrementAndDoubling {
	public:
	int N;
	int getMin(vector <int> DA) {
		int i=0;
		int r=0;
		N=DA.size();
		sort(DA.begin(),DA.end());
		if(DA[N-1]==0) return 0;
		while((1<<(r+1))<=DA[N-1]) r++;
		FOR(i,N) r+=__builtin_popcount(DA[i]);
		return r;
	}
};

まとめ

この問題はさらっと解けたので満足。