1504C - Balance the Bits - Codeforces Round #712 Div.2

• 2021年4月3日開催のCodeforces Round #712 Div.2に参加した
• ABを解いた
• Cを復習する

問題へのリンク 解説へのリンク

問題概要

括弧列構築問題。 2進数文字列$s$が与えられる。 「$s$を参照するある条件」に従ってバランスの取れた括弧列$a, b$を構築する。 条件は次。

$s_i = 1$ならば$a_i = b_i$ そうでなければ$a_i \neq b_i$

説明のためにテストケースより例を引用する。

• $s$: 101101
• $a$: ()()()
• $b$: ((()))

コンテスト中に考えたこと

1. わからん
2. $a_i$を()どちらにするかを枝刈り深さ優先探索してみるか→TLE
3. 状態「括弧列の深さ」が重複しないようにメモ化するか→TLE

解説の解法

解説を読みました。 貪欲に構築すればいい。

先頭は(、末尾は)でなければならない。 ゆえに$s$の先頭と末尾は1でなければならない。

$s$の0の数は偶数でなければならない。 $a$の(の数と$b$の(の数を同じにしなければならないので。

構築不可能な場合を除いたところで、$a,b$を構築する。

• 1は、前半の1は(、後半の1は)にすれば最適
• 0は()を交互にする

提出

提出へのリンク

提出したコードを開く

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// solve a testcase
void solve();

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

    int t;  // number of testcases
    cin >> t;
    // solve all testcases
    for (int i = 0; i < t; i++) {
        solve();
    }
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    array<int, 2> count = {};

    if (s.front() != '1' || s.back() != '1') {
        cout << "NO\n";
        return;
    }

    for (int i = 0; i < n; i++) {
        if (s[i] == '0')
            count[0]++;
        else
            count[1]++;
    }

    if (count[0] % 2) {
        cout << "NO\n";
        return;
    }

    count[1] = n - count[0];

    const array<int, 2> final_count = count;
    count = {};

    string a = string(n, 'a'), b = string(n, 'a');

    for (int i = 0; i < n; i++) {
        string pushchar = "()";

        if (s[i] == '0') {
            pushchar = (count[0] % 2 ? "()" : ")(");
            count[0]++;
        } else {
            pushchar = (count[1] < final_count[1] / 2 ? "((" : "))");
            count[1]++;
        }
        a[i] = pushchar[0];
        b[i] = pushchar[1];
    }

    cout << "YES\n";
    cout << a << "\n" << b << "\n";
}