はじめに
この記事ではbit全探索というアルゴリズムを3通りの方法で実装します。
具体的には、bit全探索を用いると解ける次の問題を3通りの方法で解いていきます。
C - たくさんの数式
この記事ではbit全探索がどのようなアルゴリズムであるかの説明はしませんので、わからない方は適宜調べてください。個人的には以下の記事がわかりやすいと思います。
これから解く問題「C - たくさんの数式」について
この問題は次のようにして解けます。
- 入力で与えられる
Sの文字と文字の間に、+を挟む方法は$2^{N-1}$通りある。 - それらすべてを列挙するためにbit全探索を行う。
- for文で回したbitの1が立っている場所を、
+を挟む場所と対応させることで個々の場合における計算結果を得る。 - それぞれの計算結果を
ansに足していく -
ansを出力する。
以下で紹介する3つの実装は、おおむねこの流れに沿ったものとなっています。
違いは列挙の仕方にあります。それでは早速見ていきましょう。
1. 素直なbit全探索
よく他の記事でも紹介されている最も一般的（だと思われる）bit全探索の実装です。
どこにbitが立っているかはシフト演算を使ってチェックしています。
S = input()
N = len(S)
ans = 0
# Sに+を挟む方法は、Sに文字と文字の間(N-1個ある)に
# それぞれ挟むか挟まないかを決めれば決まるから2^(N-1)通りある。
# それを長さN-1のbitに対応させることで全探索することで答えを求める。
# 例: S = 12345 bit = 110 なら bit = 0110 とみなして 12+3+45 を答えに足していく。
for bit in range(1 << (N - 1)): # 1 << (N-1) は 2^(N-1) と同じ
s = S[0]
for i in range(N - 1): # どこにbitが立ってるかを確認していく
if bit & (1 << i): # 下からi番目にbitが立っているとき
ans += int(s)
s = ""
s += S[i + 1]
ans += int(s)
print(ans)
この実装のポイント
- ビット演算の理解が深まる。
- 他言語に応用が効きやすい。
提出 #38119940 - AtCoder Beginner Contest 045（68ms）
2. 整数を二進数に対応させて行うbit全探索
これはあまり他の記事ではみかけない実装です。特徴的なのは次の2行です。
for b in range(2 ** (N - 1)):
bit = bin(b)[2:].zfill(N - 1)
for文で$2^{N-1}$回のループを回しているのは今までと変わりません。
ただ二行目のbit = bin(b)[2:].zfill(N - 1)で整数bを二進数に変換し、それがN-1桁になるよう0埋めをしています。
もう少し詳しく、具体例を用いてみていきましょう。
入力でS = 12345が与えられたとします。このときN = len(S) = 5です。
for文でbを0から2^{N-1}-1まで回します。
今回N = 5なのでbは0から15までを動くことになりますね。
b = 5の場合を考えてみます。
bin(b)ではbを二進数に変換しています。bin(b) = "0b101"と、変換した後は文字列の先頭に0bがついているのでこれを取っ払うためにスライスをして数字の部分だけ切り取ります。すなわち、bin(b)[2:]です。
しかし、bin(b)[2:]のままでは101であり、文字列の長さが足りていないので長さがN-1 = 4にするために0埋めをします。それをしているのが.zfill(N - 1)の部分です。
これでようやくbin(b)[2:].zfill(N - 1) = "0101"となり長さN-1=4の文字列が得られたのでこれを用いてi番目の隙間に+を挟むかどうかの判定が、i番目が1かどうかで判定できます。
S = input()
N = len(S)
ans = 0
# Sに+を挟む方法は、Sに文字と文字の間(N-1個ある)に
# それぞれ挟むか挟まないかを決めれば決まるから2^(N-1)通りある。
# それを長さN-1のbitに対応させることで全探索することで答えを求める。
# 例: S = 12345 bit = 110 なら bit = 0110 とみなして 12+3+45 を答えに足していく。
for b in range(2 ** (N - 1)):
bit = bin(b)[2:].zfill(N - 1)
s = S[0]
for i in range(N - 1): # どこにbitが立ってるかを確認していく
if bit[i] == "1": # 下からi番目にbitが立っているとき
ans += int(s)
s = ""
s += S[i + 1]
ans += int(s)
print(ans)
ポイント
- $2^{N-1}$通りの場合の数をチェックしているという実感がもてる。
- シフト操作をどう書くか覚えていなくてもよい。
提出 #38120122 - AtCoder Beginner Contest 045（78ms）
3. itertools.product()をつかったbit全探索
次はitertoolsモジュールのproduct関数を用いた実装です。
このproduct関数は引数に入れたリストの直積を重複なく出力してくれます。
今回はrepeatという引数にN-1を入れて、0と1からなる長さN-1の直積を生成するようにしています。
from itertools import product
S = input()
N = len(S)
ans = 0
# Sに+を挟む方法は、Sに文字と文字の間(N-1個ある)に
# それぞれ挟むか挟まないかを決めれば決まるから2^(N-1)通りある。
# それを長さN-1のbitに対応させることで全探索することで答えを求める。
# 例: S = 12345 bit = 110 なら bit = 0110 とみなして 12+3+45 を答えに足していく。
for bit in product((0, 1), repeat=N - 1):
s = S[0]
for i in range(N - 1): # どこにbitが立ってるかを確認していく
if bit[i] == 1: # 下からi番目にbitが立っているとき
ans += int(s)
s = ""
s += S[i + 1]
ans += int(s)
print(ans)
ポイント
- 実装をバグらせにくい。
- pythonならではの方法なので他言語に応用が効きにくい。
提出 #38120100 - AtCoder Beginner Contest 045（69ms）
おわりに
いかがだったでしょうか、実行速度的には1が68msと一番高速ですが、基本的には気に入ったモノを使えば良いと思います。（私は2が好きでよく使ってます、覚えたての頃によく書いてた癖が抜けなくて……）
間違いなどありましたら、お気軽にコメントいただけますと幸いです。
ここまで読んでいただきありがとうございました。