#1085309 (C++17) No.3143 Colorless Green Parentheses Sleep Furiously

提出ソース
結果

問題	No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー	it_is_a_pity_
提出日時	2025-05-16 22:08:16
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	43 ms / 2,000 ms
コード長	11,638 bytes
コンパイル時間	4,857 ms
コンパイル使用メモリ	273,156 KB
実行使用メモリ	22,656 KB
最終ジャッジ日時	2025-05-17 00:28:46
合計ジャッジ時間	6,313 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 49
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(v) v.begin(),v.end()
const ll INF = (ll)2e18;

#include <bits/stdc++.h>
using namespace std;

/*
Wavelet Matrix
    非負の要素の配列に対して、
        区間内である値未満/以上の値とか個数を求められる
参考
ウェーブレットツリーに関するものだが、基本的な考え方がわかる
    https://www.slideshare.net/slideshow/ss-15916040/15916040
このライブラリはdrkenさんのライブラリに様々な機能を自分で追加したものである
    https://github.com/drken1215/algorithm/blob/master/DataStructureSegment/wavelet_matrix.cpp


WaveletMatrix wm(vec);  //宣言

全てlog(max(vec))で処理できる

wm.rank(l,r,num);           [l,r)でnumである要素数

wm.range_freq(l,r,upper);   [l,r)でupper未満である要素数
wm.range_freq(l,r,lower,upper); [l,r)で[lower,upper)である要素数

wm.k_th_smallest(l,r,k);
    0-indexedでk番目に小さい[l,r)にある値
wm.k_th_largest(l,r,k)

wm.k_smallest_sum(l,r,k);
    [l,r)で小さい方からk個の和
wm.k_largest_sum(l,r,k);
    [l,r)で大きい方からk個の和

wm.prev_value(l,r,val);
    [l,r)でval未満で最大の値
wm.next_value(l,r,val);
    [l,r)でval以上で最小の値

*/

// Bit Vector (for 64-bit non-negative integer)
struct BitVector {
    // block: bit vector
    // count: the number of 1 within each block
    unsigned int n, zeros;
    vector<unsigned long long> block;
    vector<unsigned int> count;
    
    // constructor
    BitVector() {}
    BitVector(const unsigned int num) {
        resize(num);
    }
    void resize(const unsigned int num) {
        n = num;
        block.assign(((num + 1) >> 6) + 1, 0);
        count.assign(block.size(), 0);
    }
    
    // set val(0 or 1) onto i-th bit, get i-th bit of val(0 or 1)
    void set(const unsigned int i, const unsigned long long val = 1LL) {
        assert((i >> 6) < block.size());
        block[i >> 6] |= (val << (i & 63));
    }
    unsigned int get(const unsigned int i) const {
        assert((i >> 6) < block.size());
        return (const unsigned int)(block[i >> 6] >> (i & 63)) & 1;
    }
    void build() {
        for (unsigned int i = 1; i < block.size(); i++) {
            count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]);
        }
        zeros = rank0(n);
    }
    
    // the number of 1 in [0, i)
    unsigned int rank1(const unsigned int i) const {
        assert((i >> 6) < count.size());
        assert((i >> 6) < block.size());
        return count[i >> 6] +
        __builtin_popcountll(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
    }
    // the number of 1 in [i, j)
    unsigned int rank1(const unsigned int i, const unsigned int j) const {
        return rank1(j) - rank1(i);
    }
    // the number of 0 in [0, i)
    unsigned int rank0(const unsigned int i) const {
        return i - rank1(i);
    }
    // the number of 0 in [i, j)
    unsigned int rank0(const unsigned int i, const unsigned int j) const {
        return rank0(j) - rank0(i);
    }
    // the number of 0 in [0, n)
    unsigned int rank0() const {
        return zeros;
    }
};

// Wavelet Matrix (must vec[i] >= 0)
template<class T> struct WaveletMatrix {
    // inner data
    unsigned int n, height;
    vector<T> v;
    vector<BitVector> bv;
    vector<vector<long long>> sum;

    // constructor (sigma: the number of characters)
    WaveletMatrix() : n(0) {}
    WaveletMatrix(unsigned int n) : n(n), v(n) {}
    WaveletMatrix(const vector<T> &vec) : n(vec.size()), v(vec) {
        build();
    }
    void add(const T &val) {
        assert(val >= 0);
        v.push_back(val);
        n = v.size();
    }
    void set(unsigned int i, const T &val) {
        assert(i >= 0 && i < n && val >= 0);
        v[i] = val;
    }
    void build() {
        assert(n == (int)v.size());
        T mv = 1;
        for (int i = 0; i < n; ++i) mv = max(mv, v[i]);
        for (height = 1; mv != 0; mv >>= 1) ++height;
        vector<int> left(n), right(n), ord(n);
        iota(ord.begin(), ord.end(), 0);
        bv.assign(height, BitVector(n));
        sum.assign(height + 1, vector<long long>(n + 1, 0));
        for (int h = height - 1; h >= 0; --h) {
            int l = 0, r = 0;
            for (int i = 0; i < n; ++i) {
                if ((v[ord[i]] >> h) & 1) {
                    bv[h].set(i);
                    right[r++] = ord[i];
                } else {
                    left[l++] = ord[i];
                }
            }
            bv[h].build();
            ord.swap(left);
            for (int i = 0; i < r; ++i) ord[i + l] = right[i];
            for (int i = 0; i < n; ++i) sum[h][i + 1] = sum[h][i] + v[ord[i]];
        }
    }
    
    // access v[k]
    T access(int i) {
        T res = 0;
        for (int h = height - 1; h >= 0; --h) {
            int i0 = bv[h].rank0(i);
            if (bv[h].get(i)) {
                i += bv[h].rank0() - i0;
                res |= T(1) << h;
            } else {
                i = i0;
            }
        }
        return res;
    }
    T operator [] (int i) {
        return access(i);
    }
    
    // count "i" s.t. v[i] = val, i in [l, r)
    int rank(int l, int r, const T &val) {
        assert(0 <= l && l <= r && r <= n);
        for (int h = height - 1; h >= 0; --h) {
            int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if ((val >> h) & 1) {
                l += bv[h].rank0() - l0;
                r += bv[h].rank0() - r0;
            } else {
                l = l0;
                r = r0;
            }
        }
        return r - l;
    }
    
    // [l,r)で[lower,upper)である要素数、lowerは省略可
    int range_freq(int l, int r, const T &upper) {
        assert(0 <= l && l <= r && r <= n);
        int res = 0;
        for (int h = height - 1; h >= 0; --h) {
            int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if ((upper >> h) & 1) {
                l += bv[h].rank0() - l0;
                r += bv[h].rank0() - r0;
                res += r0 - l0;
            } else {
                l = l0;
                r = r0;
            }
        }
        return res;
    }
    // [l,r)で[lower,upper)である数の個数
    int range_freq(int l, int r, const T &lower, const T &upper) {
        return range_freq(l, r, upper) - range_freq(l, r, lower);
    }
    
    // the k-th (0-indexed) smallest value in [l, r)
    T k_th_smallest(int l, int r, int k) {
        assert(0 <= l && l <= r && r <= n);
        T res = 0;
        for (int h = height - 1; h >= 0; --h) {
            int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if (r0 - l0 <= k) {
                l += bv[h].rank0() - l0;
                r += bv[h].rank0() - r0;
                k -= r0 - l0;
                res |= T(1) << h;
            } else {
                l = l0;
                r = r0;
            }
        }
        return res;
    }
    
    // the k-th (0-indexed) largest value in [l, r)
    T k_th_largest(int l, int r, int k) {
        assert(0 <= l && l <= r && r <= n);
       return k_th_smallest(l, r, r - l - k - 1);
    }

    // [l, r)で小さい方からk個の和　
    T k_smallest_sum(int l, int r, int k) {
        assert(0 <= l && l <= r && r <= n);
        //もしkが区間幅よりも大きければ、区間幅まで小さくする
        k = min(k, r - l);

        if (l == r) return 0;
        T res = 0, val = 0;
        for (int h = height - 1; h >= 0; --h) {
            int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            //0のやつは全て求めるべき値に含まれている時
            if (r0 - l0 <= k) {
                l += bv[h].rank0() - l0;
                r += bv[h].rank0() - r0;
                k -= r0 - l0;
                val |= T(1) << h;
                //sumは(l,r)の状態から左に0,右に1となるように並べ替えた後の累積和になっている
                //そのため、↓で現在注目しているbitが0であるものによる和を足している
                res += sum[h][r0] - sum[h][l0];
            } else {
                l = l0;
                r = r0;
            }
        }
        //最終的に到達した場所(数)がk個残っている
        res += val * k;
        return res;
    }

    T k_largest_sum(int l,int r,int k){
        k = min(k, r - l);
        //全体-小さい方から(r-l-k)個の和
        return k_smallest_sum(l, r, r - l) - k_smallest_sum(l, r, r - l - k);
    }

    //[l,r)で[lower,upper)である要素の和
    T range_sum_by_value(int l,int r,T lower,T upper){
        int smaller_cnt = range_freq(l, r, lower);
        int MAX_element = k_th_largest(l, r, 0);
        int bigger_cnt = range_freq(l, r, upper, MAX_element + 1);
        // 全体の和-小さい方の和-大きい方の和
        return k_largest_sum(l, r, r - l) - k_smallest_sum(l, r, smaller_cnt) - k_largest_sum(l, r, bigger_cnt);
    }

    // the max value (< val) in [l, r)
    T prev_value(int l, int r, T val) {
        assert(0 <= l && l <= r && r <= n);
        int num = range_freq(l, r, 0, val);
        if (num == 0) return T(-1);
        else return k_th_smallest(l, r, num - 1);
    }
    
    // the min value (>= val) in [l, r)
    T next_value(int l, int r, T val) {
        assert(0 <= l && l <= r && r <= n);
        int num = range_freq(l, r, 0, val);
        if (num == r - l) return T(-1);
        else return k_th_smallest(l, r, num);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    if(N%2==1){
        cout << "No" << endl;
        return 0;
    }
    vector<ll> memo(N, -1);
    stack<pair<ll,char>> st;
    rep(i,N){
        if(S[i]=='('){
            st.push({i,S[i]});
        }
        else{
            if(st.size()==0){
                cout << "No" << endl;
                return 0;
            }
            else{
                memo[i] = st.top().first;
                st.pop();
            }
        }
    }
    //Sは対応が取れている
    vector<ll> depth(N+1, 0);
    rep(i,N){
        if(S[i]=='('){
            depth[i + 1] = depth[i] + 1;
        }
        else{
            depth[i + 1] = depth[i] - 1;
        }
    }
    rep(i,N){
        if(S[i]==')'){
            depth[i+1]++;
        }
    }

    // for(auto x:depth){
    //     cout << x << ' ';
    // }
    // cout << endl;

    WaveletMatrix wm(depth);

    // cout << wm.range_freq(3, 6, 2, 3) << endl;

    string ans = "";
    ll cnt = 0;
    rep(i,N){
        if(S[i]==')'){
            ll d = depth[i + 1];
            ll tmp = wm.range_freq(memo[i] + 1, i + 1, d+1, d + 2);
            tmp /= 2;
            //cout << tmp << endl;

            if(tmp==0){
                ans += "1+1";
                cnt += 2;
            }
            else if(tmp==1){
                ans += "+1";
                cnt += 1;
            }
            ans += S[i];
        }
        else{
            if(i!=0&&S[i-1]==')'){
                ans += "+";
            }
            ans += S[i];
        }
        //cout << ans << endl;
    }
    if(cnt==K&&wm.range_freq(1,N+1,1,2)==2){
        cout << "No" << endl;
        return 0;
    }

    if(cnt<=K){
        cout << "Yes" << endl;
        rep(i,K-cnt){
            ans += "+1";
        }
        cout << ans << endl;
    }
    else{
        cout << "No" << endl;
    }
}
yukicoder

結果

ソースコード
