【競プロ典型 90 問】002 - Encyclopedia of Parentheses

Arakaki Tokyo -

米田氏が企画した「競プロ典型90問」を解いていきます。

ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。 競プロ初心者なのでどうか温かい目で見守ってください。

なお、本記事中のPythonコードはブラウザ上で実行可能です。 よろしければ遊んでいってください。

問題

kyopro_educational_90/002.jpg at main · E869120/kyopro_educational_90


002 - Encyclopedia of Parentheses（★3）

やってみよう！

テストデータ・テスト関数定義　↓

# 縮小表示 test_data = [ { "in":[2], "out": "()" }, { "in":[3], "out": "" }, { "in":[4], "out": """(()) ()()""" }, { "in":[10], "out": """((((())))) (((()()))) (((())())) (((()))()) (((())))() ((()(()))) ((()()())) ((()())()) ((()()))() ((())(())) ((())()()) ((())())() ((()))(()) ((()))()() (()((()))) (()(()())) (()(())()) (()(()))() (()()(())) (()()()()) (()()())() (()())(()) (()())()() (())((())) (())(()()) (())(())() (())()(()) (())()()() ()(((()))) ()((()())) ()((())()) ()((()))() ()(()(())) ()(()()()) ()(()())() ()(())(()) ()(())()() ()()((())) ()()(()()) ()()(())() ()()()(()) ()()()()()""" } ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}")

下のmain0関数を完成させて「Run」ボタンをクリックしよう！

def main0(N): pass test_all(main0)

自由欄

try(1st.)

  • 長さNの正しいカッコ列($S_{(N)}$)って、長さN-2の正しいカッコ列($S_{(N-2)}$)に以下の3パターンを加えたものじゃね？
    • 「()$S_{(N-2)}$」
    • 「($S_{(N-2)}$)」
    • 「$S_{(N-2)}$()」
  • それだったら再帰で簡単に実装できるな。ヨユー😁
  • あかん、「$S_{(N/2)}S_{(N/2)}$」とかのパターンもあるやん…。どないしよ。
  • 💡これ、格子上のスタートからゴールまで最短経路で移動するパターンと一緒やん！

    • イメージ：「(」だと右に進む、「)」だと下に進む

という訳で実装したのが以下

def gen_kakko(n, l, r): if n == l + r: return [""] if l == r: return add_l(n, l, r) elif l == n / 2: return add_r(n, l, r) else: return add_l(n, l, r) + add_r(n, l, r) add_l = lambda n, l, r: ["("+kakko for kakko in gen_kakko(n, l+1, r)] add_r = lambda n, l, r: [")"+kakko for kakko in gen_kakko(n, l, r+1)] def main(N): if N % 2: return "" out = gen_kakko(N, 0, 0) return "\n".join(out) test_all(main)

いけそう。

結果(1st.)

提出 #32357603 - 競プロ典型 90 問

一発AC!やったー

解説

kyopro_educational_90/002.jpg at main · E869120/kyopro_educational_90

全探索してから条件に合うパターンを抽出するとのこと。
001の羊羹問題が全探索でタイムアウトだったので最初から除外してたが、ありなのか…
そこらへんのさじ加減がまだ掴めてないなぁ

try(2nd.)

解説を踏まえて実装しなおしてみます。

from itertools import accumulate, product from functools import reduce def main(N): if N % 2: return "" return "\n".join([ reduce(lambda acc, v: acc+("(" if v == 1 else ")"), pat, "") for pat in product((1, -1), repeat=N) if sum(pat) == 0 and min(accumulate(pat)) > -1 ])

まさかの2文(と言っていいのか？)で実装できてしまいました。
ちょっとコメントを加えると、

  • 9行目　全てのパターンを列挙：「(」を1、「)」を-1とする
  • 10行目　条件：「(」と「)」が同数、かつ左から足していって0より小さくならない
  • 8行目　パターンからカッコ列を生成

って感じです。

test_all(main)

サンプルケースも大丈夫そうなので提出してみます。

結果(2nd.)

提出 #32359024 - 競プロ典型 90 問

無事ACとなったものの、今回は実行時間が486 msと、1回目(78 ms)の約6倍になってしまいました。
実装の方向性が大きく変わってくるだけに、与えられた制約下でどれだけ手を抜けるか見積もれるようになることも今後の課題です。

補足

itertools.product

今回の問題では「辞書順に出力」という条件が付いていましたが、2回目のスクリプトで該当する処理はproduct((1, -1), repeat=N)です。

このパターンは辞書式順序を作り出し、入力のイテレート可能オブジェクトたちがソートされていれば、直積タプルもソートされた順に出てきます。

例

from pprint import * pp(list(product((1, -1), repeat=4)))

このように、「(」を1、「)」を-1と見立てることで最初から辞書順のパターンを作ることができます。

itertools.accumulate

まずreduceを知っていたほうが理解しやすいです。
そして一般的なreduceの説明はJavaScriptのreduce(英ページが圧倒的に詳しい！)が分かりやすいです。

その上で、このaccumulateはreduceで引き回されるaccの各時点での値を返します。
言葉では分かりづらいので以下例

例①　デフォルトで加算

list(accumulate([1, 2, 3, 4, 5]))

例②　乗算

import operator list(accumulate([1, 2, 3, 4, 5], operator.mul))

例③　年利5%で1000万円借り入れ、毎年90万円返済する場合の残高

list(accumulate([1000, -90, -90, -90, -90], lambda bal, pmt: bal*1.05 + pmt))

例④　先頭から走査してその時点での最大値

list(accumulate([3, 4, 6, 2, 1, 9, 0, 7, 5, 8], max))

自由欄