問題
http://arc061.contest.atcoder.jp/tasks/arc061_a
'1'~'9'から成る文字列Sがある。
この文字列に'+'を入れて正しい数式を作る。
全ての考えられる入れて作られる数式に対して和を取り、その総和を答えよ。
1 <= |S| <= 10
考察
1. 制約が全てを物語ってる所ある
2. まず制約から考えるとbit的な解法だろう
3. 以下、N = |S|とする
4. '+'を入れる入れないで全ての場合を考えると 2^(N-1) 通りあるので全探索できる
5. 各処理でも10桁までしか無いので、ループは10回でよい
6. O(10*2^(N-1))で間に合う
7. あとは上手いこと実装するだけ
実装
http://arc061.contest.atcoder.jp/submissions/878954
typedef long long ll; string S; int N; //----------------------------------------------------------------- int main() { cin >> S; N = S.length(); ll ans = 0; rep(i, 0, 1 << (N - 1)) { ll sm = 0; ll a = S[0] - '0'; rep(j, 0, N - 1) { if (i & (1 << j)) { sm += a; a = 0; } a = a * 10 + S[j + 1] - '0'; } sm += a; ans += sm; } cout << ans << endl; }