競技プログラミング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)[修正点]
・全探索をやめて、左かっこを先に辞書順に生成
・ビット表記を経ずに直接かっこを表記
・計算速度アップ
コメント