WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}