ABC 401-500/ABC454D - (xx) - 競技プログラミング用 知識集積所

---

問題

ABC454D

必要知識

B以下レベルの内容は省略

• 考察問題

考え方

考察問題。
問題を同等な価値を持つ考えやすい問題に書き換えていく。

まず、括弧をつけたり外したりすると問題にあるが、「ある位置の括弧をつけたあとで別のある位置の括弧を外す」という操作が可能な場合、順序を先に外す側をやることが必ずできる。
よって、問題の「括弧を付けたり外したりを何度もできる」を「何度も外す操作ができて、その後何度もつける操作ができる」にしても影響はない。

そして、「Aのある位置に括弧をつけてBと一致させる」は「Bの同じ位置の括弧を外してAと一致させる」と考えてもよい。
よって、問題は「何度も括弧をAから外す操作ができて、その後括弧をBから外す操作ができる」としてもよい。

ここまで来れば、Aから再帰的に(xx)をxxに変更した文字列とBから再帰的に(xx)をxxに変更した文字列が一致するかという問題になる。
ということは、与えられた文字列に対し再帰的に(xx)をxxに変更した文字列を返す関数を作っておき、AとBの処理後の文字列が一致するかどうかを調べればよい。

その関数は、一例として、

• 別の文字列に先頭から1文字ずつコピーで書き足していく
• コピーしようとする文字が')'だった場合、末尾3文字をチェックして、"(xx"だったら、コピーの代わりにそこを"xx"に変える

のループを作ればよい。

解答例

解答例

注意点

別解