Codeforces #184 Div2 C 「Ivan and Powers of Two」
問題
http://codeforces.com/contest/305/problem/C
訳
イワンはa1, a2, ... anというn個の非負の整数を持っている。イワンはこの配列は非減少になるようソートされていることを把握している。
イワンは2^a1 2^a2, ... 2^an となる数を紙に書き出した。この書き出した数を全て足した数値が2^v - 1 ( v >= 0 )となるよう、最小何個の2^b ( b >= 0 )を足せばよいかを出力せよ。
制約
1 <= n <= 10^5
1 <= a_i <= 2 * 10^9
考えた事
要は、配列の要素を全部足して、2進数にした時の0の数を数えろということ。しかしa_iは20億なので、素直にやるわけにはいかない。なので何ビット目が何個分あるよーというmapを持ってあげればよい。このままだと何個分のところが2を超えてしまう場合があるので、2で割って次の上位ビットにその数を足せばよい。
事後
stl::mapはイテレート中に要素を追加しても、ちゃんとそれを拾ってくれるのを初めて知った。
mapはあまり使わないので書きにくいです
あと、配列を全て足すのならソートされてるされてないっていらない情報のような。。。
ソースコード
int main() { int N; cin >> N; // 何ビット目が何個分あるか数える map<int, int> m; for( int i = 0; i < N; i++ ){ int t; cin >> t; if( m.find( t ) != m.end() ){ m[t]++; }else{ m[t] = 1; } } // ちゃんと2進数にする for( map<int,int>::iterator it = m.begin(); it != m.end(); it++ ){ int p = it->first; int n = it->second; if( n >= 2 ){ m[p] %= 2; if( m.find( p + 1 ) != m.end() ){ m[p+1] += n / 2; }else{ m[p+1] = n / 2; } } } // 0の数を数える int pp = -1; int res = 0; for( map<int,int>::iterator it = m.begin(); it != m.end(); it++ ){ int p = it->first; int n = it->second; if( n == 0 ) continue; res += p - pp - 1; pp = p; } cout << res << endl; }