競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
327: デフォルトの名無しさん (ﾜｯﾁｮｲ 469a-dFNS) [sage] 2023/06/06(火) 11:53:03.19 ID:MhCqkbZk0 某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が void parenthesis(int l, int r, string& s, vector<string>& ans) { if (l + r == 0) { ans.push_back(s); return; } if (r < l) return; if (l > 0) { s.push_back('('); parenthesis(l - 1, r, s, ans); s.pop_back(); } if (r > 0) { s.push_back(')'); parenthesis(l, r - 1, s, ans); s.pop_back(); } } （呼出の例） vector<string> ans; string s; parenthesis(4, 4, s, ans); この if (r < l) return; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に 効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り 立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが どなたかわかりやすい説明はないでしょうか http://mevius.5ch.net/test/read.cgi/tech/1679465982/327
332: デフォルトの名無しさん (ﾜｯﾁｮｲ 469a-dFNS) [sage] 2023/06/07(水) 08:33:42.08 ID:nPOLblkw0 >>327のコードとは別に、 (と)をそれぞれn個使う正当な括弧列をレベルn(L=n)の括弧列と呼んだとき、L=nの括弧列から L=n+1の括弧列はどう生成されるのかを考えてみたのですが 例えばL=2の()()はL=1の()の右か左に()を追加した、考えてみます L=3の((()))はL=2の(())に ( + (()) + ) とした、と考えてみます このように「全体を()で囲むか()を追加するかのルール」でいけるのかと思いきや L=4の(())(())がL=3のどれからどう作られるのか、がよくわからず ( + ())(() + )ができたらいいのですが ())(() はL=3の正しい括弧列ではない 例えばL=3の (())() に (()) ( + () + ) と、括弧を割り込ませる? なんだかおかしい? あるいはこれはL=2の(())を二つ並べた、と考えるべき? 要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか? あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか? などということが気になったのですが http://mevius.5ch.net/test/read.cgi/tech/1679465982/332
333: デフォルトの名無しさん (ﾜｯﾁｮｲ 012d-UlWg) [sage] 2023/06/07(水) 09:49:06.82 ID:Bta2HQ7X0 >>332 結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、 それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。 しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。 それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです： 1. '(' + P + ')' を追加する 2. P + '()' を追加する 3. '()' + P を追加する ここで P は大きさnの任意のバランスの取れた括弧列です。 この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。 ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために 何らかの方法で重複を除去する必要があります。 したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」 という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。 しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>327に示されたDFSを用いたアプローチに比べて 効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。 なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/333
337: デフォルトの名無しさん (ﾜｯﾁｮｲ 797f-Ydfh) [sage] 2023/06/10(土) 17:29:19.24 ID:0oQUevmP0 >>327 閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。 開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う http://mevius.5ch.net/test/read.cgi/tech/1679465982/337
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.016s