競プロ典型90問 [2問目] - らんこむの数学部屋

こんばんは。競プロ典型90問、2問目やっていきます。

問題文で「正しいカッコ列」なるものが定義されていますが、普段使用しているカッコ列と変わりありません。

この定義に正直に沿って解いてしまうと、文字列結合で遅くなってしまったり、重複していないか、など考えることが多くなってしまいます。

そこで、正しいカッコ列というものを

左n文字の部分文字列では「 ( 」の数が「 ) 」の数と同じかそれよりも多い
全体文字列では「 ( 」の数と「 ) 」の数が一致している

と考えました。

左から文字列を形成していき、一つ目の条件を満たさなくなった場合には文字列の形成を中断してしまえば、生成されるカッコ列に対して線形オーダーで生成することができました。 emplace_string関数では、文字列に対してまだ閉じていないカッコの数を記録しておくことで一つ目の条件を判断しています。

#include <iostream>
#include <string>

using namespace std;

void emplace_string(string S, int N, int cnt) {
    
    if (S.size() == N) {
        if (cnt == 0) {
            cout << S << endl;
        }
        return;
    }
    
    if (cnt == 0) {
        emplace_string(S + "(", N, cnt + 1);
    }
    else {
        emplace_string(S + "(", N, cnt + 1);
        emplace_string(S + ")", N, cnt - 1);
    }

}

int main() {

    int N;
    cin >> N;

    if (N % 2 != 0) {
        // 奇数なら存在しない
        return 0;
    }

    // 偶数の場合
    string S = "";
    emplace_string(S, N, 0);

    return 0;

}

結構綺麗にまとまったと思ったのですが、実行時間はあまり早くはなかったです。

アルゴリズム的にはこれ以上早くなる余地はないかと思うのですが、プログラムの書き方次第でもそれなりに変動するようです。

もっとプログラムとお友達にならないといけませんね。