AtCoder ABC 045 C - たくさんの数式 (ARC 061 C) (緑色, 300 点)

AtCoder 版蟻本に bit 全探索の最初の例題として、この問題を挙げていたので。

問題へのリンク

問題概要

"231"

といった 1〜9 の数値で構成された、長さ の文字列 が与えられる。文字列の隙間に '+' を挿入する方法は 通りある。そのそれぞれについての計算結果を合計した結果を求めよ。

制約

• 

考えたこと

通りの場合を、 bit を用いた全列挙で、全列挙して求めることができる。bit 全探索はここに。

drken1215.hatenablog.com

今回は「N-1 箇所ある隙間のうち、どこに区切りを入れるか」を bit 全探索で列挙する。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = S.size();
    long long res = 0;
    for (int bit = 0; bit < (1<<(N-1)); ++bit) {
        long long tmp = 0;
        for (int i = 0; i < N-1; ++i) {
            tmp *= 10;
            tmp += S[i] - '0';
            if (bit & (1<<i)) res += tmp, tmp = 0;
        }
        tmp *= 10;
        tmp += S.back() - '0';
        res += tmp;
    }
    cout << res << endl;
}