今回は競プロ典型90問の「002 – Encyclopedia of Parentheses」について書きます。
執筆理由は前回同様で解説を見ないと解けなかったためです。
今のところ典型90問は全敗なうえ最近コンテスト参加もできていないため、ちゃんとレベル上げしていきたい所です。
今回も本記事では公式の解説の説明と提出コードを載せていきます。
今回の解説のキーワードは「小さい制約は全探索を考えよう」でした。
今回考える文字列では「(」と「)」の2文字しか登場しないため、文字列を2進数に変換できます。
制約の最大値である20でも通り数は2^20 ≒ 10^6となります。
1秒に探索可能な候補数は10^8程度と言われているため、余裕で全探索できると推測できます。
(探索可能な候補数は「アルゴリズム実技検定 公式テキスト［エントリー～中級編］」, p95より引用)
候補文字列を全探索できそうなので、次はどうやって解となる文字列であるか判定する方法を考えます。
こちらは文字列の先頭から’(‘を1、’)‘を-1として順に足していき、以下の条件を全て満たせば解となる文字列となります。
個人ブログの方に実際にACしたコードを載せました。
興味のある方はご覧ください。
【競プロ】競プロ典型90問 – 002 – Encyclopedia of Parentheses
入会申込
ログイン
