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

コメント歓迎です。
前回の力まかせ探索と異なり、ビット全探索を使います。
初めてのビット全探索でしたので苦戦しました。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

arc061.contest.atcoder.jp

方針

入力例１の「125」を例にとると、出力値は125+(1+25)+(12+5)+(1+2+5)で「176」です。
この例では入力は3桁なので'+'が入る位置は1と2の間か2と5の間の2箇所のみです。
つまりパターンとしては、それぞれの位置に'+'が入るか、入らないかで考えればよく、例1の場合は4パターンとなります。

この4パターンを2桁の2進数で表現すると、
00, 01, 10, 11
となります。

ここで、0は「'+'が入らない」、1は「'+'が入る」と関連付けることで全探索できます。

まず"00"の場合、'+'は一度も入りませんので「125」を表現することを考えます。
後々、'+'が入るパターンを考えたとき「125」という文字列を一桁ずつ処理していった方が都合が良さそうです。

今回は一番左の「1」から処理するとして、まず一時的な計算値を保持する変数tmpに記録しておきます。
1桁ずつ処理していく方針なので、次の処理としてはtmpの値を「1」から「12」としたいと考えます。

つまり「'+'が入らない」場合の処理は、現在保持している値を10倍して次の桁の値を加算すればよいということになります。
この処理を繰り返すことで「125」を表現できました。

次に"01"の場合、「1+25」を表現することを考えます。
まず、一番左の「1」を変数tmpに記録しておく部分は同様です。

ここで「'+'が入る」という処理が必要になります。
'+'が入ってきたとき、最終的に求めたい値は「176」ですから、tmpの値「1」はそのまま合計に加算します。
さらにtmpの値を「2」にできれば「'+'が入らない」場合の処理と合わせて残りは自動で計算できます。

tmpの値を2にする処理は、一度tmpに0を代入し、「'+'が入らない」場合の処理を行うことで処理を使いまわして実現できます。

コード(AC)

#include <iostream>
using namespace std;

int main(){
  // 入力
  string S; // 数字の文字列
  long long tmp = 0; // 一時的な計算値を保持する変数
  long long sum = 0; // 合計

  cin >> S; 

  int digit = S.size() - 1; // 入力文字列の桁数 - 1

  // ビット全探索 ビットパターン 2^(digit)
  for (int i = 0; i < (1 << digit); ++i) {
    tmp = S[0] - '0'; // 文字列から数値に変換して保持
    // ビットパターンと'+'が入る位置を関連付け
    // "1":'+'が入る "0":'+'が入らない
    // '+'が入るか一桁ずつ確認
    for (int j = 0; j < digit; ++j) {
      // '+'が入ったら保持値を合計に足し、0を代入
      if (i & (1 << j)) {
        sum += tmp;
        tmp = 0;
      }
      // '+'が入らなかったら保持値を10倍して次の桁を加算
      tmp = tmp * 10 + S[j + 1] - '0';
    }
    sum += tmp;
  }
  // 出力
  cout << sum << endl;
}