WARush

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

Codeforces #171 Div2 E "Beautiful Decomposition"

問題

整数Sが2進数表記の文字列で与えられる。
2^k(k >= 0)を足したり引いたりして整数Sにする時、
足したり引いたりする回数の最小を返せ。

制約

1 <= Sの文字数 <= 10^6

考えた事

DPっぽいが、Tagにあるように貪欲にいける。

基本的には'1'になっている所の分だけ足していけばいいのだが、
Sampleの"111"や"1011011"の時に、あえてその数値よりも
大きい数値を足して回数を節約している。
これを"おっきい数足すぞテクニック"と呼ぶ。

このテクニックは1が2つ以上続いている場合有効である。

例えば、"111101111"の時、まずおっきい数"100000000"を足す。
そして0の所を1とした"10000"で引くと、

1000000000
    -10000 
 -----------
 111100000

となり、1を4つも消化できるのだ。
普通に1を足していったら4回のところ
テクニックを使うと2回に抑えられる。
そして残りの"1111"もテクニックを駆使すれば
あと2回でよさそうだ。

しかしちょっと待って欲しい。
"111101111"の'0'の所まで'1'がくるように
"1000"を引くとどうだろう。

1000000000
     -1000
 ----------
 111110000

となり、なんとおっきい数がもう足された状態になり、
すぐにでもテクニックが使える状態にできるのだ。

これは"おっきい数足すぞチェイン"と呼ばれる高等テクニックだ。
このチェインは'0'が2つ以上続いていなければ使える。

この2つのテクニックを使えば、0が2個以上続いていない部分を
ひとまとまりとして扱い、回数を最大限節約できる。

つまり例の"111101111"は3回で作れてしまうのだ。
素直に1を足していったら8回かかると考えると凄い節約である。


しかし、このテクニックを使う上で1つだけ注意点がある。
それは、まとまりの中に1が2個以上続いている部分が全くなければ、
このテクニックは返って回数を増やしてしまうと言う事だ。

例えば、
"10101"でテクニックを使うと4回足したり引いたりする事になるが、
素直に1を足してけば3回ですむ。

1が続いていなければ素直に足していこう。


f:id:Ekaing:20130309231214j:plain

ソースコード
const int MAX_LEN = static_cast<int>(1e6);
char str[MAX_LEN+1];

int main() {
    
    cin >> str;
    int n = strlen( str );

    int res = 0;
    int i = 0;
    int one, zero, seg = 0;
    bool flg = false; // 1が続いたところはあったか?
    while( i < n ){
        // 1が続くところまで読み込み
        one = 0;
        while( i < n && str[i] == '1' ){
            one++; i++;
        }
        seg++;
        if( one >= 2 ) flg = true;

        // 0が続くところまで読み込み
        zero = 0;        
        while( i < n && str[i] == '0' ){
            zero++; i++;
        }

        // 0が連続してた、もしくはiが最後まで行ったら計算
        if( i >= n || zero >= 2 ){
            if( flg ){
                res += seg + 1;
            }else{
                res += seg;
            }
            seg = 0; flg = false;
        }
    }
    cout << res << endl;
}