競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
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
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.019s