【典型90問】 成長記録 #002

典型90問 002 - Encyclopedia of Parentheses（★3）

概要としては長さN列のカッコ列を出力する問題。
方針だけ解説で見たところbit全探索のアルゴリズムを用いて解くっぽい。

bit全探索とは

〇×のような、それぞれ二つの選択肢がある問題に対して、すべての組み合わせを1~nとすると、二進数に変換したときに1と0ですべての組み合わせを表すことができる。このようなアルゴリズムをbit全探索という。
一般的に全探索するため要素数がn≦20程度の場合に用いる。
基本的なbit全探索の型は以下のサイトを参考にして学んだ。

Python bit全探索を簡単にやるコツ

脳筋コード

n = int(input())
k = []　   #生成した配列を格納するリスト

for i in range(2 ** n):
  if i == 0:
    continue
  l = 0
  ans = True
  for j in range(n):
    if (i >> j) & 1:
      l += 1
    else:
      l -= 1
    if l < 0:
      ans = False
      break
  if ans and l == 0:
    l = ''
    for j in range(n):
      if (i >> j) & 1:
        l += '('
      else:
        l += ')'
    k.append(l)  

k.sort()
for i in k:
  print(i)

感想

アルゴリズムを使わないと解けない問題を初見で解けたのはこれが初めてなので大きな一歩だと思う。
これからも地道に頑張りたい...!
あと最近atcoderをやっていて思うのが、いかにループの中で無駄な処理を減らせるかが処理速度に大きく影響するという事。