競プロ典型90問：002 - Encyclopedia of Parentheses（★3）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_b

挑戦結果

• 解けた
• 時間：20分ぐらい

考えたこと

• すべて列挙なのでループして求める
• N文字なら、開カッコがN/2個、閉カッコがN/2個
• 閉じカッコが先行する場合がNG
• (と)の全順番を$2^N$パターン作成してチェックするのもアリかと思ったけど、再帰的にOKパターンだけ作れそうな気がした
• 方針
• 左から確定していき全パターンを保持。(と)の数を持ちつつ、末尾に追加していく。

振り返り

• とりあえず解けたのは良かった。
• 解説は「ステップ1：bit全探索」＋「ステップ2：'(' - ')(の累積計算」だった。自分はステップ2を思いついていなかった。
• 解説を読んだあとにbit全探索版でもやってみたら、TLEになった。
• pypy3 なら通った

コード

# インプット
N = int(input())

# n：残りの長さ
# op:( の数
# cl:) の数
# L：現時点でリストアップしているカッコ文字列のリスト
# 戻り値：カッコ文字列のリスト
def f(n, op, cl, L):
    # 残りが0文字なら、Lを返す
    if n==0:
        return L
    ret = []
    # カッコが開いてるときは、閉じカッコを末尾に追加可能
    if op > cl:
        L1 = [s+')' for s in L]
        ret += f(n-1, op, cl+1, L1)
    # 開きカッコを使い切ってなければ、開くカッコを末尾に追加可能
    if op < N//2:
        L2 = [s+'(' for s in L]
        ret += f(n-1, op+1,cl, L2)
    return ret

# Nが奇数のときはNG
ans = []
if N%2==0:
    # 初期値は長さNの文字列が欲しい、開きカッコも閉じカッコも0、既存リストは空文字。
    ans = f(N, 0, 0, [""])
# ソート
ans.sort()

# 結果の出力
for a in ans:
    print(a)

ソース(解説読んだあとにBit全探索版で書き直し)

# インプット
N = int(input())

# i番目のビットが立っているか
BIT_LENGTH = N
def isOne(bit_pat, i):
    return (bit_pat & 1 << (BIT_LENGTH - 1 - i)) > 0

# 結果用
ret = []

# bit全探索で全パターン列挙
for bit_ptn in range(1<<N):
    # 開きカッコを+1、閉じカッコを-1でカウント
    kakko_cnt = 0
    # カウントがマイナスになったらNGになる
    isOK = True
    # カッコの開きと閉じをカウント
    for i in range(N):
        if isOne(bit_ptn, i):
            kakko_cnt += 1
        else:
            kakko_cnt -= 1
        # 一時的にでもマイナスになったらNG 
        if kakko_cnt < 0:
            isOK = False
    # 開きカッコと閉じカッコの数が同数ならOK
    if isOK and kakko_cnt==0:
        # bitから文字列に変換
        s = ""
        for i in range(N):
            if isOne(bit_ptn, i):
                s += "("
            else:
                s += ")"
        ret.append(s)
# ソートして出力
ret.sort()
for s in ret:
    print(s)