kmjp's blog

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

TopCoder SRM 596 Div1 Easy IncrementAndDoubling

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

問題

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

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

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

解法

1増やすより2倍する方が効率が良い。
よって、各数列要素については、2倍を繰り返しながら途中の桁が1になるタイミングで1増やせばよい。
2倍繰り返す回数は、最大値の最大桁数になるので、回答は(全要素の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;
	}
};

まとめ

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

広告を非表示にする