結果

問題 No.684 Prefix Parenthesis
ユーザー qwewe
提出日時 2025-05-14 13:21:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 2,733 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 125,872 KB
最終ジャッジ日時 2025-05-14 13:23:53
合計ジャッジ時間 6,039 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N = int(sys.stdin.readline())
    S_char_list = sys.stdin.readline().strip()

    s_params_list = []

    running_balance = 0
    # min_balance_in_prefix_scan: min balance encountered while scanning S_str[0...j]
    # this value is relative to balance 0 at the start of S_str[0...j]
    min_balance_in_prefix_scan = 0 
    running_num_close = 0

    for j in range(N): # For prefix S_str[0...j], which is S_{j+1}
        char_s_j = S_char_list[j]
        
        if char_s_j == '(':
            running_balance += 1
        else: # char_s_j == ')'
            running_balance -= 1
            running_num_close += 1
        
        # min_balance_in_prefix_scan should be the minimum balance encountered
        # if we scanned S_str[0...j] starting from balance 0.
        # The running_balance tracks sum of (+1 for '(', -1 for ')').
        # min_balance_in_prefix_scan tracks min value of this sum over current prefix.
        min_balance_in_prefix_scan = min(min_balance_in_prefix_scan, running_balance)
        
        # Parameters for S_{j+1} = S_str[0...j]
        final_bal_val = running_balance
        
        # c_k = max(0, -min_balance_of_Sk_starting_from_0)
        # min_balance_in_prefix_scan is min( B[0], B[1], ..., B[j] ) where B are prefix sums
        # We need min(0, B[0], ..., B[j]) for c_k calculation.
        # Example: S_k = "((", min_balance_in_prefix_scan might be 1 (if S_str starts with '(').
        # But for "((", c=0. If S_k="))((" min_balance_in_prefix_scan could be -2.
        # The current running_min_balance is correct for definition of min_balance_in_Sk.
        
        c_val = max(0, -min_balance_in_prefix_scan) 
        p_val = final_bal_val + c_val
        m_val = running_num_close - c_val
        
        s_params_list.append({'c': c_val, 'm': m_val, 'p': p_val})

    list_1 = [] # p_i >= c_i
    list_2 = [] # p_i < c_i

    for params in s_params_list:
        if params['p'] >= params['c']:
            list_1.append(params)
        else: 
            list_2.append(params)
            
    # Sort list_1: by c_i ASC, then p_i DESC
    list_1.sort(key=lambda x: (x['c'], -x['p']))
    
    # Sort list_2: by p_i DESC, then c_i ASC
    list_2.sort(key=lambda x: (-x['p'], x['c']))

    sorted_full_list = list_1 + list_2
    
    total_pairs = 0
    current_open_brackets_count = 0

    for params in sorted_full_list:
        c = params['c']
        m = params['m']
        p = params['p']

        can_satisfy_c = min(c, current_open_brackets_count)
        total_pairs += m + can_satisfy_c
        current_open_brackets_count = current_open_brackets_count - can_satisfy_c + p
        
    sys.stdout.write(str(total_pairs * 2) + "\n")

solve()
0