Src/Random/RandomBalancedParenthesis.hpp

• View this file on GitHub
• Last update: 2025-09-06 12:13:55+09:00
• Include: #include "Src/Random/RandomBalancedParenthesis.hpp"
• Link: https://codeforces.com/blog/entry/103245

Depends on

• Src/Random/RandomDistinctArray.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/Random/RandomConnectedGraph.hpp
• Src/Random/RandomTree.hpp

Code

#pragma once

#include "./RandomDistinctArray.hpp"

#include <algorithm>
#include <cassert>
#include <vector>
#include <random>
#include <string>

namespace zawa {

namespace Random {

// https://codeforces.com/blog/entry/103245
std::string BalancedParenthesis(usize n, bool verify = true) {
    if (n == 0)
        return "";
    auto left = DistinctArray<usize>(n, 0, 2 * n, verify);
    std::string gen(2 * n + 1, ')');
    for (usize i : left)
        gen[i] = '(';
    std::vector<i32> pref(gen.size());
    pref[0] = gen[0] == '(' ? +1 : -1;
    for (usize i = 1 ; i < pref.size() ; i++)
        pref[i] = pref[i - 1] + (gen[i] == '(' ? +1 : -1);
    auto sp = std::ranges::min_element(pref) - pref.begin();
    std::string res(2 * n, '(');
    for (usize i = 0 ; i < 2 * n ; i++)
        res[i] = gen[(sp + 1 + i) % gen.size()];
    if (verify) {
        i32 bal = 0;
        for (u8 c : res) {
            assert(c == '(' or c == ')');
            bal += c == '(' ? +1 : -1;
            assert(bal >= 0);
        }
        assert(bal == 0);
    }
    return res;
}

} // namespace Random

} // namespace zawa

#line 2 "Src/Random/RandomBalancedParenthesis.hpp"

#line 2 "Src/Random/RandomDistinctArray.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Random/RandomDistinctArray.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>

#include <iostream>

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<T> DistinctArray(usize n, T min, T max, bool verify = true) {
    assert(min <= max);
    assert(n <= static_cast<usize>(max - min + 1));
    std::mt19937_64 mt{std::random_device{}()};
    std::vector<T> res(n);
    std::unordered_map<T, T> mp;
    for (T& v : res) {
        T val = static_cast<T>(mt() % (max - min + 1)) + min;
        T replace = [&]() {
            auto it = mp.find(max);
            return it == mp.end() ? max : it->second;
        }();
        auto it = mp.find(val);
        if (it == mp.end()) {
            v = val;
            mp[val] = replace;
        }
        else {
            v = it->second;
            it->second = replace;
        }
        max--;
    }
    if (verify) {
        assert(std::ranges::all_of(res, [&](T v) { return min <= v and v <= static_cast<T>(max + n); }));
        assert(std::unordered_set<T>(res.begin(), res.end()).size() == n);
    }
    return res;
}

} // namespace Random

} // namespace zawa
#line 4 "Src/Random/RandomBalancedParenthesis.hpp"

#line 9 "Src/Random/RandomBalancedParenthesis.hpp"
#include <string>

namespace zawa {

namespace Random {

// https://codeforces.com/blog/entry/103245
std::string BalancedParenthesis(usize n, bool verify = true) {
    if (n == 0)
        return "";
    auto left = DistinctArray<usize>(n, 0, 2 * n, verify);
    std::string gen(2 * n + 1, ')');
    for (usize i : left)
        gen[i] = '(';
    std::vector<i32> pref(gen.size());
    pref[0] = gen[0] == '(' ? +1 : -1;
    for (usize i = 1 ; i < pref.size() ; i++)
        pref[i] = pref[i - 1] + (gen[i] == '(' ? +1 : -1);
    auto sp = std::ranges::min_element(pref) - pref.begin();
    std::string res(2 * n, '(');
    for (usize i = 0 ; i < 2 * n ; i++)
        res[i] = gen[(sp + 1 + i) % gen.size()];
    if (verify) {
        i32 bal = 0;
        for (u8 c : res) {
            assert(c == '(' or c == ')');
            bal += c == '(' ? +1 : -1;
            assert(bal >= 0);
        }
        assert(bal == 0);
    }
    return res;
}

} // namespace Random

} // namespace zawa

Back to top page