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

競技プログラミング
Page content

まえがき

今回は競プロ典型90問の「002 - Encyclopedia of Parentheses」について書きます。
執筆理由は前回同様で解説を見ないと解けなかったためです。
今のところ典型90問は全敗なうえ最近コンテスト参加もできていないため、ちゃんとレベル上げしていきたい所です。

今回も本記事では公式の解説の説明と提出コードを載せていきます。

解法の解説

今回の解説のキーワードは「小さい制約は全探索を考えよう」でした。
今回考える文字列では「(」と「)」の2文字しか登場しないため、文字列を2進数に変換できます。
制約の最大値である20でも通り数は$2^{20} \fallingdotseq 10^6$となります。
1秒に探索可能な候補数は$10^8$程度と言われているため、余裕で全探索できると推測できます。
(探索可能な候補数は「アルゴリズム実技検定　公式テキスト［エントリー～中級編］」, p95より引用)

候補文字列を全探索できそうなので、次はどうやって解となる文字列であるか判定する方法を考えます。
こちらは文字列の先頭から’(‘を1、’)‘を-1として順に足していき、以下の条件を全て満たせば解となる文字列となります。

  • 和が途中で0未満にならない
  • 最終的な和が0である

反省

今回は回答となる文字列が何らかの数値に対応しそうということまでは思いつきました。
しかしその数値の列に何らかの法則があり、計算などで出せると考えたため詰まりました。

今回は制約を見て全探索可能と判断できなかったことと、勝手に法則性があると考えたことが敗因だと思います。
普通は全探索する方が楽なため、解き始めに全探索可能か確認する癖をつけた方が良さそうです。

提出コード

#include <bits/stdc++.h>

#define rep(i, n) for (auto i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()

using namespace std;

using ll = long long int;

string bits_to_string(int N, const bitset<20>& bits) {
    vector<char> chars(N);
    rep(i, N) chars[i] = bits[i] ? ')' : '(';
    reverse(ALL(chars));

    return string(ALL(chars));
}

bool judge_string(const string& s) {
    int counter = 0;
    for (char c : s) {
        counter += c == '(' ? 1 : -1;

        if (counter < 0) return false;
    }

    return counter == 0;
}

int main() {
    int N;
    cin >> N;

    rep(i, (ll)pow(2, N)) {
        bitset<20> bits(i);

        string s = bits_to_string(N, bits);

        if (judge_string(s)) cout << s << endl;
    }

    return 0;
}