こちらの記事の「bit全探索」をやってみた。
目次
- 目次
- bit全探索とは
- ABC061 C - たくさんの数式
- ABC079 C - Train Ticket
- ABC104 C - All Green
- ARC029 A - 高橋君とお肉
- ABC002 D - 派閥
bit全探索とは
例えば["hoge", "fuga", "piyo"]というリストがあってこれらすべての組み合わせを網羅的に列挙したいときにbit全探索が役に立つ。
組み合わせを網羅的に列挙とは下記パターンを列挙すること (左側の数字はただのインデックス番号、真ん中はインデックス番号をbitで表したもの)
0 : 0 : [ ] 1 : 1 : [ hoge ] 2 : 10 : [ fuga ] 3 : 11 : [ hoge fuga ] 4 : 100 : [ piyo ] 5 : 101 : [ hoge piyo ] 6 : 110 : [ fuga piyo ] 7 : 111 : [ hoge fuga piyo ]
このとき真ん中のbitが立っている位置と組み合わせで選ばれているもののリストのインデックス番号が一致している。
(1 : 1 : [ hoge ]は0bit目が立っている。hogeはリストのインデックス0の値。)
bitの立っている位置を組み合わせを列挙したいリストのインデックスとして利用することで全探索が可能になる。これをbit全探索と呼ぶらしい。
先の出力をするコードは以下のようになる。
w = ["hoge", "fuga", "piyo"] n_bit = len(w) for bit in range(1 << n_bit): # 1 << n_bit == 2 ** n_bit arr = [] for i in range(n_bit): if bit & (1 << i): # bitの立っている位置を確認 arr.append(w[i]) # ここはprintしているだけなのでbit全探索とは関係ない print(f'{bit} : {bin(bit).replace("0b", ""):>3} : [ ', end='') for a in arr: print(a, end=' ') print(']')
リストの要素数がn個のとき、組み合わせ数は2**nになる。
この例では要素数が3なので2**3 == 8個の組み合わせがprintされる。(8個の中には空集合も含む)
bit全探索が何者か分かったので冒頭のQiitaの記事にあるAtCoderの問題を解いてみる。
ABC061 C - たくさんの数式
問題
125みたいな文字列Sが与えられたときに、 (Sは10文字以内)+を使って考えられる数式を全て作り、- その計算結果の合計値を出力しなさい
という問題
125を例にすると125、1+25、12+5、1+2+5 という4通りがある。
解答
+記号は文字の間にしか入れられないので、文字の間に+を入れるか入れないかを全探索する。(bitが立っていたら+を入れる、立っていなかったら+を入れない。)+を入れられる隙間の数は文字列の長さ-1なので、125の場合は2箇所に+を入れることができる。この2箇所に対して全探索するので（この例では）式は2**2 == 4個の組み合わせがでる。Pythonでは組み込み関数の
evalを使うことで文字列の式を評価できる。(intで結果を返してくれる。)
print(eval("1+1")) # 2
解答コード
s = input() n = len(s) - 1 total = 0 for bit in range(1 << n): siki = s[0] for i in range(n): if bit & (1 << i): siki += '+' siki += s[i + 1] total += eval(siki) print(total)
ABC079 C - Train Ticket
問題
1222みたいな文字列が与えられたときに、+と-記号を使って、- 答えが7になる式を出力しなさい
という問題
各文字列間に必ず
+か-を入れなくてはいけない。
解答
- 「ABC061 C - たくさんの数式」と同様に文字間に
+を入れるか、-を入れるかを全探索する。
s = input() def solve(): # 答えがでたときにループを抜けるのが面倒くさかったので関数にしてある l = len(s) - 1 for bit in range(1<<l): siki = s[0] for i in range(l): if bit & (1<<i): siki += "+" else: siki += "-" siki += s[i+1] if eval(siki) == 7: siki += "=7" print(siki) return solve()
ABC104 C - All Green
この問題は難しくて解けなかった...
C - All Green
問題
- 目標スコアGと問題数piとその問題数を全て解いた時にもらえるボーナスciが与えられた時に
- 目標スコア以上の点数になるためには最低何問の問題を解けばよいか出力しなさい という問題 ボーナスという設定がなければ、点数の高い問題から解いていけばよいが、ボーナスをうまく利用すると点数の低い問題を解くだけで最短で目標点数を達成することがある。
解答
- ボーナスを獲得したパターンを全探索すればいいらしい。
- 目標点数に達していない場合は、これに加えて点数の高い問題から解いていく。このときボーナスが発生するまで解く必要はない。ボーナスが発生するパターンは全探索するから。)
D, G = map(int, input().split()) P = [] C = [] for _ in range(D): p, c = map(int, input().split()) P.append(p) C.append(c) ans = [] for bit in range(1<<D): total_score = 0 solved = 0 # ボーナスを獲得するパターンを全探索 for i in range(D): if bit & (1<<i): total_score += C[i] + ((i+1)*100) * P[i] # 解いた問題の点数 + ボーナスを加算 solved += P[i] # まだ目標点数に達していない場合は点数の高い問題を解いていく for i in range(D - 1, -1, -1): if G <= total_score: ans.append(solved) break # bitが立っている問題はすでに解いてあるのでskip if bit & (1<<i): continue s = (i+1) * 100 required_score = G - total_score # 目標達成までに必要な点数 required_problem = (required_score + s - 1) // s # 目標達成までに解く必要のある問題数 total_score += min(required_problem, P[i]-1) * s # ボーナスが発生しないようにP[i]-1 で1問解かないようにする solved += min(required_problem, P[i]-1) if G <= total_score: ans.append(solved) break print(min(ans))
ARC029 A - 高橋君とお肉
問題
- N個のお肉があって、(各お肉には焼けるまでの時間が設定されている)
- 2つの肉焼き器を使った場合に最短で全てのお肉が焼けるまでの時間を出力しなさい という問題
解答
- お肉を2つの肉焼き器のうちどちらで焼くかを全探索すればいい
- bitが立っているお肉は肉焼き器1、bitが立っていないお肉は肉焼き器2みたいな感じ
n = int(input()) arr = [int(input()) for _ in range(n)] ans = float("inf") for bit in range(1<<n): device1 = [] device2 = [] for i in range(n): if bit & (1<<i): device1.append(arr[i]) # 肉焼き器1にお肉を置く else: device2.append(arr[i]) # 肉焼き器2にお肉を置く elaps = max(sum(device1), sum(device2)) ans = min(ans, elaps) print(ans)
ABC002 D - 派閥
解けなかった...
D - 派閥
問題
- 議員の関係性(どの議員とどの議員が知り合いか)が与えられて、そこから派閥の最大数を求めよ
という問題
派閥はすべての議員同士が知り合いでなければいけない。
解答
- 議員の最大数が12人程度なので派閥を全探索していけばいいらしい
- 全探索で議員の組み合わせを作り、そこからその組み合わせの派閥が成り立つかをチェックしていく
N, M = map(int, input().split()) con = [[False] * N for _ in range(N)] for i in range(M): x, y = map(int, input().split()) con[x-1][y-1] = True con[y-1][x-1] = True ans = 0 for bit in range(1<<N): ok = True cnt = bin(bit).count('1') # bitの数が派閥に所属する議員数 if cnt <= ans: continue for i in range(N): for j in range(N): if bit & (1<<i) and bit & (1<<j) and \ i != j and not con[i][j]: # con[i][j]がTrueのときお互いが知り合いである ok = False if ok: ans = cnt print(ans)
