bit全探索

はい。

最初に書いておくとしばらくこの記事を参考にアルゴリズムを体系的に勉強していこうと考えています。

というわけで、しばらくは焼き増しになってしまうかもしれないけどしょうがないよね。

qiita.comqiita.com

今回はbit全探索の紹介。
典型的な問題がこれ。

atcoder.jpatcoder.jp

bit全探索は個々の要素に2つの状態が決められて、それを全探索したいときに便利。

今回の問題では、

といった感じに全探索したい。

まず、必要になるのが '+' 入れる入れないを01で表す、という発想である。
次に01で表すならバイナリで表せるんじゃないか？という考えが必要になる。この考えが 'bit' 全探索と呼ばれる理由だ。たぶん

今回の '+' を入れたい箇所はn-1個になる。
よって、

for i in range(2**(n-1)):

で2**(n-1)回す。

まず、2進表記がどうなっているのか見てみよう。

n=3
for i in range(2**(n-1)):
  print(bin(i))

# 出力
0b0
0b1
0b10
0b11

なるほど。
この最初についている0bはこれが二進表記、バイナリだよという事を伝えている。
01の組み合わせも全部できてるっぽい。

次に0か1か、つまり '+' を入れるか入れないかの判断をしたい。
ここでbit演算という処理を行う。こっちがbit全探索って言われる理由だな、うん。
bit演算て何？という事だが、そもそもやりたかったのが2進表記の何桁目が1/0なのかを知りたいという事である。、さあどうやって何桁目が1/0か判別しようか。

ビット演算にビットシフトというものがある。
指定した数だけビットを右、もしくは左にずらす処理を行う事だ。……つまり、どういうことだ？
やってみよう。

n=3
for i in range(2**(n-1)):
  for j in range(n-1):
    print(bin(i),bin(i>>j))
  print('-------')

# 出力
0b0 0b0
0b0 0b0
-------
0b1 0b1
0b1 0b0
-------
0b10 0b10
0b10 0b1
-------
0b11 0b11
0b11 0b1
-------

なるほど！こういう事か！！！

とはならない気がするので説明。
今回右に1ビットシフトしているので、0b10→0b1のように、1ずつ右にずれていく。
なのであとは、&演算子を使って一番下のビットを比較して1かどうか調べればおｋ

自分が提出したコードはこんな感じ

s=input()

n=len(s)
ans=0
for i in range(2**(n-1)):
  num=''
  for j in range(n):
    num+=s[j]
    if i>>j & 1:
      num+='+'
  ans+=eval(num)
print(ans)