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

問題

問題概要

省略。

解法

bit全探索。sの長さがnのとき、n-1個の場所に+を入れることができるので、+を入れる場所を2^n-1通り全部試せばいい。実装方法は、bitを使い、1であればその部分に+を入れて、0であればその部分に+を入れない。例えば、s=125の場合、 mask= 00(0)~11(2)を試せばいい。
00(0) : 125
01(1) : 12 + 5
10(2) : 1 + 25
11(3) : 1 + 2 + 5

ミス

なし

コード

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

//positionbit目が立っているか判定
bool contain(int mask, int position){
    if((mask & (1 << position)) != 0) return true;
    else return false;
}

int main(void){
    string s; cin >> s;
    int n = s.size() - 1;
    
    ll sum = 0;
    for(int mask = 0; mask < (1 << n); ++mask){
        int l = 0;//左端
        ll tmp = 0;
        int r;//右端
        for (r = 0; r < n; ++r){
            if(contain(mask, r)){
                string t = s.substr(l, r - l + 1);
                ll num = stoll(t);
                tmp += num;
                l = r + 1;
            }
        }
        string t = s.substr(l, r - l + 1);
        ll num = stoll(t);
        tmp += num;
        sum += tmp;
    }
    printf("%lld\n", sum);
    return 0;
}