arc061 c bit全探索 atcoder

ARC061 C - たくさんの数式

ARC061 C - たくさんの数式
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/arc061/tasks/arc061_a

数字列が与えられるので、その任意の位置に任意の数だけ$+$を入れで出来るすべての数式の答えの和を求める問題.

解説

数字列の長さ$S$が$10$と小さいので、bit全探索で計算ステップ数は$2^{10}$と十分間に合う.
数字列を再帰的に先頭一文字と残りに分割していき、その合計を求める.
数え上げの漏れだけないように注意.

計算量

数字列の長さを$S$とすると、

$$O(2^S)$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <sstream>
string S;

void input() {
  cin >> S;
}

Int dfs(string s) {
  stringstream ss(s);
  Int x = 0;
  ss >> x;
  if (s.length() == 1) return x;
  loop(n,1,s.length()) {
    string left = s.substr(0, n);
    string right = s.substr(n);
    stringstream ss2(left); Int leftNum = 0; ss2 >> leftNum;
    Int rightNum = dfs(s.substr(n));
    // i.e. 1 + 23
    //      1 + 2 + 3
    // Here '1 +' is added twice. (twice is the number of cases)
    x += leftNum * pow(2, right.length()-1) + rightNum;
  }
  return x;
}

void solve() {
  cout << dfs(S) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}