#1083679 (C++17) No.684 Prefix Parenthesis

• 問題: No.684 Prefix Parenthesis
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:55:47
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,423 bytes
• コンパイル時間: 905 ms
• コンパイル使用メモリ: 81,392 KB
• 実行使用メモリ: 16,064 KB
• 最終ジャッジ日時: 2025-05-14 12:56:52
• 合計ジャッジ時間: 8,658 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
other	AC * 4 TLE * 2 -- * 25

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

using namespace std;

// Structure to hold information about prefix S_i
struct PrefixInfo {
    int id; // Original index (1 to N) of the prefix S_i
    int len; // Length of the prefix S_i, which is equal to i
    long long bal; // Balance = count('(') - count(')') in S_i
    long long min_bal; // Minimum balance over all prefixes of S_i (including the empty prefix with balance 0)
    long long open_count; // Count of '(' characters in S_i
    long long close_count; // Count of ')' characters in S_i
};

// Global pointer to the input string S to avoid copying it multiple times
const string* global_S_ptr; 

/**
 * @brief Comparison function for sorting prefixes.
 * 
 * This function defines the sorting order for the prefixes S_1, ..., S_N.
 * The goal is to find an order of concatenation T = S_{\pi(1)}...S_{\pi(N)}
 * such that the minimum prefix balance of T is maximized. This is known to help
 * in problems related to balanced parentheses formation.
 * 
 * The comparison logic is based on checking which order (A then B, or B then A)
 * yields a better (higher) minimum prefix balance for the combined string AB or BA.
 * A prefix X comes before prefix Y if the minimum balance achieved by concatenating X then Y 
 * is greater than or equal to the minimum balance achieved by concatenating Y then X.
 * Specifically, X precedes Y if min(minB(X), bal(X) + minB(Y)) >= min(minB(Y), bal(Y) + minB(X)).
 * 
 * Tie-breaking rules are applied if the primary comparison yields equality.
 * First, based on balance (higher balance preferred).
 * Second, based on original index (lower index preferred for stability).
 */
bool comparePrefixes(const PrefixInfo& a, const PrefixInfo& b) {
    // Calculate the minimum balance if A is concatenated before B
    long long min_a_b = min(a.min_bal, a.bal + b.min_bal);
    // Calculate the minimum balance if B is concatenated before A
    long long min_b_a = min(b.min_bal, b.bal + a.min_bal);
    
    // Prefer the order that results in a higher minimum balance
    if (min_a_b != min_b_a) {
        return min_a_b > min_b_a; 
    }
    
    // Tie-breaking rule 1: Prefer prefix with higher balance. This is a heuristic choice.
     if (a.bal != b.bal) {
         return a.bal > b.bal; 
    }

    // Tie-breaking rule 2: Use original index to ensure stability and deterministic order.
    return a.id < b.id; 
}

/**
 * @brief Computes matches and final open count for processing prefix S[0...len-1]
 * starting with an initial open parenthesis count `k`.
 * 
 * This function simulates the standard greedy algorithm for finding the length
 * of the longest balanced parenthesis subsequence on the given prefix.
 * 
 * @param len The length of the prefix S_i to process (which is i).
 * @param k The initial count of open parentheses before processing this prefix.
 * @return A pair {matches, final_k}, where `matches` is the number of pairs matched
 *         during processing this prefix, and `final_k` is the open parenthesis count
 *         after processing this prefix.
 */
pair<long long, long long> process_prefix(int len, long long k) {
    long long current_k = k; // Start with the given open count
    long long matches = 0; // Initialize matches count for this prefix
    const string& S = *global_S_ptr; // Access the global input string S

    // Iterate through the characters of the prefix S[0...len-1]
    for (int i = 0; i < len; ++i) {
        if (S[i] == '(') {
            // Increment open count for '('
            current_k++;
        } else { // S[i] == ')'
            // If there's an open parenthesis available, match it
            if (current_k > 0) {
                current_k--; // Decrease open count
                matches++; // Increment matched pairs count
            }
            // If current_k is 0, this ')' cannot be matched and is ignored.
        }
    }
    // Return the total matches found within this prefix simulation and the final open count
    return {matches, current_k};
}


int main() {
    // Use fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Length of the string S
    cin >> N;
    string S; // The input string of '(' and ')'
    cin >> S;
    global_S_ptr = &S; // Set the global pointer to S

    // Vector to store information about each prefix S_1, ..., S_N
    vector<PrefixInfo> prefixes(N);
    long long current_bal = 0; // Running balance
    long long current_min_bal = 0; // Running minimum balance seen so far
    long long current_open = 0; // Running count of '('
    long long current_close = 0; // Running count of ')'
    
    // Calculate properties for each prefix S_i = S[0...i-1]
    for (int i = 0; i < N; ++i) {
        // Update counts and balance based on the current character S[i]
        if (S[i] == '(') {
            current_bal++;
            current_open++;
        } else {
            current_bal--;
            current_close++;
        }
        // Update the minimum balance encountered up to this point
        current_min_bal = min(current_min_bal, current_bal);
        
        // Store the calculated properties for prefix S_{i+1}
        prefixes[i].id = i + 1;
        prefixes[i].len = i + 1;
        prefixes[i].bal = current_bal;
        prefixes[i].min_bal = current_min_bal;
        prefixes[i].open_count = current_open;
        prefixes[i].close_count = current_close;
    }

    // Sort the prefixes based on the custom comparison function `comparePrefixes`
    sort(prefixes.begin(), prefixes.end(), comparePrefixes);

    long long total_matches = 0; // Accumulator for total matched pairs across all prefixes
    long long current_k = 0; // State variable: current count of open parentheses

    // Iterate through the sorted prefixes and simulate the greedy matching process
    for (int i = 0; i < N; ++i) {
        const PrefixInfo& p = prefixes[i]; // Get the current prefix info
        
        // Optimization: Check if the current open count `current_k` is sufficient
        // to handle the potential balance drop within this prefix `p`.
        // The minimum balance `p.min_bal` represents the largest dip. `p.min_bal` is <= 0.
        // `-p.min_bal` is the minimum initial `k` needed to ensure `k` never drops below 0 during processing `p`.
        // If `current_k >= -p.min_bal`, the open count will never reach 0 when a ')' is encountered.
        // Thus, all ')' characters in `p` will be matched.
        if (current_k >= -p.min_bal) {
             // O(1) update: All ')' in this prefix find a match.
             total_matches += p.close_count; 
             // Update the open count state by adding the balance change of this prefix.
             current_k += p.bal; 
        } else {
            // Optimization condition failed. Must simulate the processing of this prefix.
            // This step takes O(p.len) time.
            pair<long long, long long> result = process_prefix(p.len, current_k);
            // Add the matches found during the simulation.
            total_matches += result.first;
            // Update the open count state to the final count after simulation.
            current_k = result.second;
        }
    }

    // The final result is twice the total number of matched pairs, as each pair has length 2.
    cout << total_matches * 2 << endl;

    return 0;
}