0427進捗

Atcoder典型90問 002 - Encyclopedia of Parentheses

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

問題

長さ
N の正しいカッコ列をすべて、辞書順に出力してください。

ただし、正しいカッコ列は次のように定義されています :

() は正しいカッコ列である
<==>

• S が正しいカッコ列であるとき、文字列 '(' + S + ')' は正しいカッコ列である
• S,T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
• それ以外の文字列はすべて、正しいカッコ列でない

例えば、

()()
(()())(())
()()()()()()()()
は正しいカッコ列ですが、

)(
)))()(((
((((a))))
は正しいカッコ列ではありません。

また、 ( の方が ) よりも辞書順で早いものとします。

制約

1 \leq N \leq 20 \\
N \in \mathbb{N}

試したこと

• 2の20乗は100万くらいなので全探索は計算量ギリギリ。for文の中でも処理を行うことを考えると最低限探索範囲は絞りたい。
• とりあえずNの中の'('と')'の個数は絞り込めるので、実際の探索対象は N Comb (N/2)。
• 正しいカッコ文かどうかはwhile & replaceで行える。O(N)なので耐えると判断。
• 「正しいカッコ文」に対して探索をかけるか、「"("の個数だけは最低限絞り込んだカッコ文」に対して探索をかけるかが難しい。ただ前述したように正しいかどうかの判定がロジックと計算量の面でともに余裕があるのと、正しいカッコ文を綺麗に数え上げるアルゴリズムが思いつかなかったので後者を選択。
• itertoolsの存在を知らなかった。これ知らなくて15分くらい沼った。

適切な方針

• 模範解答はよくわからなかったので我流の解説を書きます。
• Nの中の'('と')'の個数はともにN /2個と絞り込めるので、実際の探索対象は N Conb (N /2)。これに対して探索をかける。
• このとき、探索対象を「N文字の'('の中から、N /2個 を')'に置き換えたstring」の集合と読み替えたのがうまくいった。置き換え対象の選び方は、0からN-1までのintを順番に格納したlに対してitertools.combinationsで組み合わせ列挙を行うことでtupple型で得られるので、あとは各選び方について該当部分のindexを')'に書き換えればよい。
  • (例) N = 4のときは 4つの'('から2つを')'に書き換えればよいので、itertools.combinationsに[0, 1, 2, 3]から2つを選んだ選び方のiteratorを返してもらい、それをindexとして
    • (0, 1) => ))((
    • (0, 2) => )()(
    • ...と書き換えを行い、順番に探索対象の文字列(cur_S)を生成していけばよい。
• 辞書順に出力するのに、このアルゴリズムだと逆順になってしまうのに気づかず出力して1ペナ
• 自力で解いたけど1時間くらいかかってしまった。permutationとcombinationがitertoolsを使えば即出せるということは知っておくべきだと思った。

解説付きコード

import itertools
anslist = []
N = int(input())

#偶数の時のみ処理を行う
if N % 2 == 0:
  #lは後で使う
  l = range(N)
  #書き換え前の文字列に対応する配列Sを作成
  S = ["(" for i in range(N)]
  # N/2 個は '('、 N/2 個は ')'
  # N個のうち N/2個を")"に書き換えた文字列を生成する
  p_itr = itertools.combinations(l, N // 2)
  for p in p_itr:
    #配列はアドレスで持っているので単純な代入は許されないことに注意
    cur_S = S.copy()
    #tupple pの各要素をindexとして、該当部分を'('から')'に書き換える
    for k in p:
      cur_S[int(k)] = ")"
    #コピーと検索が面倒なので文字列にする
    cur_S = "".join(cur_S)
    check_S = cur_S
    #正しいカッコ文かどうかの判定
    while ("()" in check_S ):
      check_S = check_S.replace("()", "")
    #除去できない余り文字がある→正しいカッコ文ではない
    if len(check_S) > 0:
      continue
    else:
      anslist.append(cur_S)
#辞書順にするのを忘れない
anslist.reverse()
for s in anslist:
  print(s)