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が続いていなければ素直に足していこう。
ソースコード
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; }