bit全探索問題まとめ

bit全探索

inp = [x for x in input()]
op_cnt = len(inp)-1

for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt
    for j in range(op_cnt):
        if ((i >> j) & 1):
            print('i: %d'%i) #0~7
            print('j: %d'%j) #0~2
            print('index: %d'%(op_cnt - 1 - j)) #配列に格納するindex
            op[op_cnt - 1 - j] = "+"
    print(op)

わかりやすいbit全探索(Python版)がまとめられていた。
qiita.com

応用問題1

これを応用して似た問題を解いてみた。
「たくさんの数式(C問題)」
atcoder.jp

inp = [x for x in input()]
cnt = len(inp)-1
sum_ = []

for c in range(2**cnt):
  inp_ = inp.copy()
  for j in range(cnt):
    if ((c >> j)&1):
      inp_[cnt-j-1]+='+'
      
  a = eval(''.join(inp_))
  sum_.append(a)
print(sum(sum_))

1≤|S|≤10なので隙間n=9。
最大でn*2**n=9*2**9=1024の計算量を要する事になります。
このサイズの計算量だと、一般的な挿入ソートと同規模らしいです。
qiita.com

応用問題を解き次第、随時更新していきます。