Codeforces #184, C : Ivan and Powers of Two

問題文

http://codeforces.com/contest/305/problem/C

概要

n 個の非負整数の列 a が与えられ、 の値を紙に書き出す。
この作業の後、更に の値を書き足すことができる。
紙に書かれた数の和を にするために追加で書かなければならない数は最小でいくつか。

解法

ビットレベルで考えると、作りたい数はすべてのビットが立っている数です。
は一つのビットが立っている数なので、これを加えることで一つのビットを立てることができます。
入力で与えられる 2 の冪乗の和のビット表現が分かれば、寝ているビットの数を数えることで答えが求まります。
しかし、数を直接扱ってしまうと指数が大きくオーバーフローしてしまうので工夫が必要です。
指数に着目することで、数を直接的に扱わずに処理をすることができます。

与えられた数を重複しない指数を使って の和で表すとしましょう。
このとき、項数と立っているビットの数が等しくなります。
入力のままでは指数が重複するので、指数に関する次の性質を利用して重複を排除します。

はじめに各指数がいくつあるのかを数えておいて、小さい方から繰り上げていくことで指数の重複を取り除くことができます。
この処理のあと、最大の指数 + 1 が二進表記での桁数になり、そこから存在している指数の数を引くとビットが寝ている桁の数が分かります。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

#define fst first
#define snd second

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	set<int> nums( ALL( as ) );
	map<int,int> counts;
	FOR( target, nums )
	{
		auto poss = equal_range( ALL( as ), target );
		counts[ target ] = distance( poss.fst, poss.snd );
	}

	FOR( c, counts )
	{
		if ( 2 <= c.snd )
		{
			counts[ c.fst + 1 ] += c.snd / 2;
			counts[ c.fst ] %= 2;
		}
	}

	int maxc, cone = 0;
	FOR( c, counts )
	{
		maxc = c.fst;
		cone += c.snd;
	}
	
	cout << maxc + 1 - cone << endl;

	return 0;
}