Last active
February 20, 2019 10:00
-
-
Save lapla-cogito/1004856ef1f44a8100b76ff406eed9d7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int main() { | |
int N, ans = 0; | |
cin >> N; | |
//bitの長さは2N | |
N *= 2; | |
//括弧列が条件を満たしているかのチェック | |
bool bye; | |
//bit全探索 | |
for (int bit = 0; bit < (1 << N); ++bit) { | |
//le='('=bitの1、ri=')'=bitの0に対応 | |
int le = 0, ri = 0; | |
bye = false; | |
for (int i = 0; i < N; ++i) { | |
if (bit&(1 << i)) { | |
++le; | |
} | |
else { | |
++ri; | |
} | |
//もし'('の数よりも')'の数が多くなったら対応の取れない括弧列なので弾く | |
if (le < ri) { | |
bye = true; | |
break; | |
} | |
} | |
//'('の数と')'の数が等しく、bye==falseならそれは対応の取れた括弧列 | |
if (le == ri && !bye) { ++ans; } | |
} | |
cout << ans << endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment