bit全探索 とは 2^n通りの全探索
例題 ARC061：たくさんの数式
1 以上 9 以下の数字のみからなる文字列 S が与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。このようにして出来る全ての文字列を数式とみなし、和を計算することができます。ありうる全ての数式の値を計算し、その合計を出力してください。
制約
・ 1≤|S|≤10
・ S に含まれる文字は全て 1 〜 9 の数字
入力出力例
[in] 125
[out] 176
# 125、1+25、12+5、1+2+5 の４パターンが考えられる。
考え方
125だったら"+"を入れられる場所は2箇所(1 {a} 2 {b} 5)ですので2^2=4通りの数式が考えられるわけです。abそれそれ"+"を入れるか入れないかの二択が二回。
そしてbitというくらいですのでbitが立っている箇所を探します。イメージとしては以下のような感じ。
| index | a | b |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
全部で４パターンあるのがわかりますね。
pythonでの実装
pythonのビット演算子 右シフト「>>」 bitAND「&」 を使います。
ビット演算子の詳細はこちらがとても参考になりました。
- 右シフト >>
11を1ビット右にシフトしてみます。一番右の1が消え一番左に0が挿入されます。
1011 = 11
0101 = 5
- bitAND &
10 & 12のbitANDを取ってみます。(位ごとに両方１になっているところだけ１を残します。)
1010 = 10
1100 = 12
1000 = 08
# 入力：１２５
s = ["1", "2", "5"]
n = len(s)
for i in range(2 ** (n-1)):
tmp = [False] * (n-1)
for j in range(n-1):
if i >> j & 1:
tmp[j] = True
pattern.append(tmp)
print(pattern)
[[False, False], [True, False], [False, True], [True, True]]
bit全探索でパターンを全て見つけることができました。
ちなみに僕が解いた例題の解答はこんな感じです。(コード汚いしもっとスマートな解き方があるはずですが）
簡潔な書き方
コメントでいただいた簡潔なコードの書き方です。
上記のコードはbit全探索を理解するという意味では良いかもしれませんが、毎回書くのは億劫になので、コンテスト中は以下の書き方がベストでしょう。
from itertools import product
list(product([False, True], repeat=3))#2^3通り
[(False, False, False), (False, False, True), (False, True, False), (False, True, True),
(True, False, False), (True, False, True), (True, True, False), (True, True, True)]