ARC061-C たくさんの数式

問題

C - たくさんの数式 / Many Formulas

考察

|S|≤10なので全ての文字列の隙間に'+'を入れるか、いれないかのO(2^n)通り試せば間に合う。

O(2^n)通りを試す方法は再帰、bit全探索の2つあるが、bit全探索の方がforループでシンプルに書けるのでbitで書く方が良いだろう。(という個人的な感想)

long long型となるのでオーバーフローしないよう気を付けたい。 (特にに0LLを渡すのは忘れがち)

コード

#include<iostream>
#include<string>
#include<numeric>
using namespace std;
 
string S;
long long a[11];
 
int main(){
    cin>>S;
    int si=S.size();
    
    long long sum=0;
    
    //bit全探索
    for(long long bit=0; bit<(1<<(si-1)); bit++){
        
        //a[]の初期化
        for(int i=0; i<si; i++)a[i]=S[i]-'0';
        
        //どこに'+'を入れるか
        for(int i=0; i<si-1; i++){
            if(bit & (1<<i)){
                //'+'をiとi+1の間に入れない
                a[i+1]=a[i]*10+a[i+1];
                a[i]=0;
            }
        }
        
        sum+=accumulate(a,a+si,0LL);
    }
    
    cout<<sum<<endl;
    return 0;
}