競プロ典型90問 002(★3) next_permutation

002 - Encyclopedia of Parentheses（★3）

問題

長さNの正しいカッコ列を出力する。

条件

• () は正しい。
• Sが正しいとき、 ( + S + ) は正しい。
• S,Tが正しいとき、文字列 S + T は正しい。
• ( の方が ) よりも辞書順で早いものとする。

解法

まず奇数の場合は何も出力しない。

Nの半分ずつを ( と) で埋めた文字列を作る。

左から順に見ていって ( の数より ) の数が多くなったら条件を満たさない。

後は逐一 () の確認をしながら next_permutation で辞書順に出力していく。

(())()　　 # OK
())(()  # NG

所感

辞書順に出力するという条件から next_permutation を使用したが、bit全探索でも求められるみたい。

むしろそっちが本筋だったと思うので、気が向いたときに解き直してみたい。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

    if (n % 2 == 1) return 0;
    string s;
    rep(i,n / 2) s.push_back('(');
    rep(i,n / 2) s.push_back(')');

    do
    {
        int cnt = 0;
        rep(i,n)
        {
            if (s[i] == '(') cnt++;
            if (s[i] == ')') cnt--;
            if (cnt == -1) break;
        }
        if (cnt == -1) continue;
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}