はまやんはまやんはまやん

hamayanhamayan's blog

たくさんの数式 / Many Formulas [ARC 061, ABC 045 C]

問題

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;
}