bit全探索

• n個それぞれに二択の選択肢をすべて探索したい
• 2**n通りのチェック

問題

002 - Encyclopedia of Parentheses（★3）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programmi

pythonコード

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])

キーポイント

python
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にするため