ABC045C - たくさんの数式

C - Many Formulas

考え方

文字列$S$の長さを$N$とすると，$N-1$箇所に$+$を入れる方法を全通り試せばよい．これはbit全探索で実現できる．

最終的に求めたいのは総和なので，

1. $+$の直後の文字列から次に$+$が出るまでの文字列を記憶し，
2. $+$が出たら，それまで記憶していた文字列を数値に変換して総和に加算し，
3. 記憶していた文字列をリセットする

とすればよい．

【回答例（リスト）】

S = input()
N = len(S)

ans = 0
for i in range(1 << (N - 1)):
  tmp = [S[0]]
  for j in range(N - 1):
    if i & 1 << j:
      ans += int(''.join(tmp))
      tmp = [S[j + 1]]
    else:
      tmp.append(S[j + 1])
  else:
    ans += int(''.join(tmp))
    
print(ans)    

【回答例（文字列）】

S = input()
N = len(S)

ans = 0
for i in range(1 << (N - 1)):
  tmp = S[0]
  for j in range(N - 1):
    if i & 1 << j:
      ans += int(tmp)
      tmp = S[j + 1]
    else:
      tmp += S[j + 1]
  else:
    ans += int(tmp)
    
print(ans)

別解

再帰関数をつかう．