結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー Today03
提出日時 2025-05-17 13:28:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 2,572 bytes
コンパイル時間 2,897 ms
コンパイル使用メモリ 282,968 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2025-05-17 13:28:52
合計ジャッジ時間 5,259 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i, a, b) for(ll i=(ll)(a); (a)<(b) ? i<(b) : i>(b); i+=((a)<(b) ? 1 : -1))

template<typename T> int LB(vector<T> v, T x) { return lower_bound(ALL(v),x)-(v).begin(); }
template<typename T> int UQ(T& v) { sort(ALL(v)); v.erase(unique(ALL(v)),v.end()); return v.size(); }
template<typename T> bool chmax(T &a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T &a, T b) { return a>b ? a=b, true : false; }
template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using ld=long double; using ull=unsigned long long; using lll=__int128_t;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;

#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif

//----------------------------------------------------------

bool IsValidBrackets(string s) {
    int tmp=0;
    for(char c:s) {
        if(c=='(') tmp++;
        else tmp--;
        if(tmp<0) return false;
    }

    return tmp==0;
}

VVI MakeTreeFromBrackets(string s) {
    s="("+s+")";
    int n=s.size()/2;

    int idx=-1;
    VVI ret(n);

    auto dfs=[&](auto&&dfs, int &pos)-> int {
        pos++; idx++;
        int now=idx;
        while(s[pos]!=')') ret[now].push_back(dfs(dfs,pos));
        pos++;
        return now;
    };
    int pos=0;
    dfs(dfs,pos);

    return ret;
}

int main() {
    int N,K; cin>>N>>K;
    string S; cin>>S;

    if(!IsValidBrackets(S)) {
        cout<<"No"<<endl;
        return 0;
    }

    //葉っぱは2,子供の個数が1の頂点も1
    auto g=MakeTreeFromBrackets(S);
    int tmp=0;
    string ans;

    auto dfs=[&](auto&&dfs, int now)-> void {
        if(now!=0) ans+="(";
        for(int nxt:g[now]) {
            dfs(dfs,nxt);
            ans+="+";
        }
        if(g[now].size()) ans.pop_back();
        if(g[now].size()==0) {
            tmp+=2;
            ans+="1+1";
        }
        if(g[now].size()==1) {
            tmp++;
            ans+="+1";
        }
        if(now!=0) ans+=")";
        return;
    };
    dfs(dfs,0);

    if(tmp>K) {
        cout<<"No"<<endl;
        return 0;
    }

    while(tmp<K) {
        tmp++;
        ans+="+1";
    }

    cout<<"Yes"<<endl;
    cout<<ans<<endl;
}
0