2021/11/13
C - たくさんの数式をpythonで解く
問題
問題のリンク↓
https://atcoder.jp/contests/arc061/tasks/arc061_a
1 以上 9 以下の数字のみからなる文字列Sが与えられるので、文字と文字の間に+ を入れて出来る数式を全パターン洗い出し、総和を求めるというもの。
125が与えられた場合
- 125
- 12 + 5
- 1 + 25
- 1 + 2 + 5
の総和を求めれば良い。
解き方
最初再帰で解いていこうとしたが、bit全探索という概念を知る。
色々記事は見つかるが、これがわかりやすかった。↓
Python de アルゴリズム（bit全探索）
今回で言えば、フラグが立っているところで文字列と文字列の間に+を入れていけば良さそう。
先ほどの例と同じく125が与えられた場合、
| 10進数 | 2進数 | パターン |
|---|---|---|
| 0 | 00 | 125 |
| 1 | 01 | 12 + 5 |
| 2 | 10 | 1 + 25 |
| 3 | 11 | 1 + 2 + 5 |
のように全パターンが洗い出せる。
各桁に対して+を付与する/しないを決めていくので、ループ数は (len(n) -1) ** 2
動作を軽く確かめる
S = input()
n = len(S) -1
for i in range(n ** 2):
print("ループ", i, "回目")
f = S[0] # この場合は1
for j in range(n):
if i >> j & 1:
f += '+' # 文字列に+を付与
f += S[j + 1] # 次の数を追加
print(f)結果
ループ 0 回目
125
ループ 1 回目
1+25
ループ 2 回目
12+5
ループ 3 回目
1+2+5想定通り、うまく出来ている。
あとは+区切りで配列にして、sumした結果を足し合わせれば良さそう。
S = input()
n = len(S) -1
ans = 0
for i in range(2 ** n):
f = S[0]
for j in range(n):
if i >> j & 1:
f += '+'
f += S[j + 1]
ans += sum(map(int, f.split('+')))
print(ans)