競プロ典型90問 自習2

スポンサーリンク
AtCoder
スポンサーリンク

競技プログラミングAtCoderのレベルアップのため、競プロ典型問題をPythonで解いていきます。
時間対効果を最大にするために以下のスキームで行います。
①問題を見る②10分だけ自力で考える③解説をみる④解説を見ながら、周辺知識を補完して、自力でコードを書く⑤問題を解く⑥他の方のコードを見て参考にして学習する⑦ブログにまとめる

002 – Encyclopedia of Parentheses(★3)

キーワード:「ビット表記」、「正しいかっこ列の条件」

自分のコード(AC後)

from sys import stdin
input = stdin.readline
# 入力
N = int(input())

for i in range(2**N):
    num_str = format(i, '0{}b'.format(N))
    if len(num_str.replace("0",""))==len(num_str.replace("1","")):
        cnt_one = 0
        cnt_zero = 0
        for i in range(len(num_str)):
            if num_str[i] == "1":
                cnt_one += 1
                if cnt_one > cnt_zero:
                    break
            else:
                cnt_zero +=1
        else:
            num_chr = num_str.replace("0","(").replace("1",")")
            print(num_chr)

[ポイント]
・解説通り全探索で全然間に合った
・0と1が同数は分かりやすいが、これまでに出た0>これまでに出た1の条件は知らないとと気付けなさそう

見直し後の解答

from sys import stdin
input = stdin.readline
# 入力
N = int(input())

ansers = []

def add_p(s, l, r):
    # 左かっこと右かっこの数の合計がNになった時、
    # 左かっこと右かっこの数が同数ならリストに追加
    if l + r == N:
        if l == r:
            ansers.append(s)
        return
    # 左かっこが多いか同数のときのみかっこを追加
    if l >= r:
        add_p(s+"(", l+1, r) # まずは左かっこ
        add_p(s+")", l, r+1) # 次に右かっこ
    return

add_p("", 0, 0)

for ans in ansers:
    print(ans)

[修正点]
・全探索をやめて、左かっこを先に辞書順に生成
・ビット表記を経ずに直接かっこを表記
・計算速度アップ

コメント