atcoder 競プロ典型90問 002 - Encyclopedia of Parentheses
2022.03.06
bit全探索
- n個それぞれに二択の選択肢をすべて探索したい
- 2**n通りのチェック
問題
https://atcoder.jp/contests/typical90/tasks/typical90_b
pythonコード
n = int(input())
items = []
for bit in range(2**n):
cnt = 0
teststr = ""
for i in range(n):
if (bit >> i) & 1:
teststr += "("
cnt += 1
else:
teststr += ")"
cnt -= 1
if cnt < 0:
break
if cnt == 0:
items.append(teststr)
items.sort()
for i in range(len(items)):
print(items[i])
キーポイント
for bit in range(2**n):
cnt = 0
teststr = ""
for i in range(n):
if (bit >> i) & 1:
(bit >> i) & 1で{下から(i+1)桁目が1かどうか`をチェックbit >> iでbitをi桁分ずらしてる。& 1が必要なのは0 or 1にするため
