結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
コンテスト
ユーザー D M
提出日時 2026-01-16 11:14:53
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,252 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,000 ms
コンパイル使用メモリ 340,396 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-16 11:15:00
合計ジャッジ時間 7,430 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    // まず括弧列チェック
    int bal = 0;
    for (char c : S) {
        if (c == '(') bal++;
        else {
            bal--;
            if (bal < 0) {
                cout << "No\n";
                return 0;
            }
        }
    }
    if (bal != 0) {
        cout << "No\n";
        return 0;
    }

    string ans;
    ans.reserve(4LL * K + 2LL * N);

    // st.back() = 現在開いている括弧の「中に存在する項数」
    vector<int> st;
    int top_terms = 0;      // 最上位（括弧の外）の項数
    int ones = 0;           // f(E) = 1 の総数（評価値）

    for (char c : S) {
        if (c == '(') {
            // 新しい「項」（括弧で始まる項）を現在レベルに追加する
            if (st.empty()) {
                if (top_terms > 0) ans.push_back('+');
                top_terms++;
            } else {
                if (st.back() > 0) ans.push_back('+');
                st.back()++;
            }
            ans.push_back('(');
            st.push_back(0);
        } else { // ')'
            // この括弧の中が 2 項以上になるまで "1" を追加
            while (st.back() < 2) {
                if (st.back() > 0) ans.push_back('+');
                ans.push_back('1');
                ones++;
                st.back()++;
                if (ones > K) { // もうKを超えたら不可能
                    cout << "No\n";
                    return 0;
                }
            }
            ans.push_back(')');
            st.pop_back();
        }
    }

    // Sは非空（N>=1）なので、最終形は単純な足し算にする必要があり、最上位も 2項以上必要
    while (top_terms < 2) {
        ans += "+1";
        ones++;
        top_terms++;
        if (ones > K) {
            cout << "No\n";
            return 0;
        }
    }

    // 余った分は最上位に +1 を足して調整（g(E)は変わらない）
    while (ones < K) {
        ans += "+1";
        ones++;
    }

    cout << "Yes\n" << ans << "\n";
    return 0;
}
0