bit全探索
ARCのC問題をときます
bit全探索というのを使うらしいです
arc061.contest.atcoder.jp
最初見たときは再帰関数でしか実装の仕方がわからなかったので、bitを使って全探索する方法をしらべました。
すると二進数のbitを区切りに見立てて0x0000000〜0x1111111の範囲を全部調べれば良いことがわかりました
区切りが出てくるまで数字を加算して
区切りが出て来たら数字を整形、全体の和に足すみたいな感じです
書いたコード
#include<iostream> #include<cstdlib> #include<string> #include<vector> using namespace std; int i,j,k; string s; vector<long int> nums; long int sum; long int fac;//+で区切られた数 int main(){ cin>>s; //各桁の値をnumsに格納 for(i=0;i<s.length();i++)nums.push_back(stoi(s.substr(i,1))); //全パターン for(i=0;i< 1<<(nums.size()-1);i++){ //1パターン //cout<<endl<<i<<"---------"<<endl; fac=0; for(j=0;j<nums.size();j++){ fac+=nums[j]; if(((i>>j)&1)==1){ sum+=fac; //cout<<fac<<endl; fac=0; }else{ fac*=10; } } //cout<<fac/10<<endl; sum+=fac/10; //cout<<endl<<i<<endl; } cout<<endl<<sum; return 0; }
これでなんでACできたかわかりませんがまあまあ短く書けました
