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

問題

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

考え

入力を文字列として受け取り，それについてどこに+を入れるか全探索すればACとなる。

例えば"125"を受け取った時，

• "1" + "25"
• "12" + "5"
• "125" ...

のように+を挟んでいくが，これは文字列"125"に関して数字の間に+を入れていくことに対応する。 つまり，"1/2/5"のように考えて，/に+を入れるかあるいは入れないかを考えていけばよい。

ただ，実装は難しかった。自分はまず/の数を数えて（xとする），0 ~ 2^xに対して全探索をする。そして，0 ~ 2^xの中のあるiについて 0, 1の1bitで構成される文字列に対応させた。つまり，"125"が入力として/の数は2であり，i = 1とすると01という文字列（s）を対応させた。これにより，このときの数字の和としては，12 + 5に対応している。同様にi = 2ならば，s = "10"であり，数字の和は1 + 25となる。

愚直にfor文をx重に回してもいいとは思ったけれど，少しかっこ悪いよね笑。

Accepted Program

#include <iostream>
#include <algorithm>
#include <bitset>
#include <string>
using namespace std;

string to_binString(int value, int length) {
  string h;
  if (value == 0) {
    h = "0";  
  }  
  while (value != 0) {
    if ((value & 1) == 0) {
      h.insert(h.begin(), '0');  
    }    
    else {
      h.insert(h.begin(), '1');  
    }
    value >>= 1;
  }
  // hを0詰めする
  while (length != h.size()) {
    h.insert(h.begin(), '0');  
  }
  return h;
}

int main () {
  string h;
  cin >> h;
  if (h.size() == 1) {
    cout << stoi(h) << endl;
    return 0;  
  }
  long long forloop = 1;
  for (int i = 0; i < h.size() - 1; i++) {
    forloop *= 2;  
  }
  long long ans = 0;
  for (long long i = 0; i < forloop; i++) {
    string s = to_binString(i, h.size() - 1);
    long long before = 0;
    long long sub = 0;
    for (long long j = 0; j < s.size(); j++) {
      if (s[j] == '1') {
        sub += stol(h.substr(before, j - before + 1));
        before = j + 1;     
      }  
    }
    sub += stol(h.substr(before, h.size() - before));
    ans = ans + sub;
  }
  cout << ans << endl;
}