結果

問題 No.3144 Parentheses Modification and Rotation (01 Ver.)
コンテスト
ユーザー Nauclhlt🪷
提出日時 2025-03-27 15:29:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,838 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 20,352 KB
最終ジャッジ日時 2025-03-27 15:29:07
合計ジャッジ時間 5,760 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 23 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

def solve():
    N = int(input())
    S = input()
    # N が奇数なら有効な括弧列にはならない
    if N % 2 == 1:
        print(-1)
        return

    # A[i] = 1 if S[i]=='(', -1 if S[i]==')'
    A = [1 if ch=='(' else -1 for ch in S]
    
    # 累積和 C[0...2N] (S を 2 回連結した形)
    C = [0]*(2*N+1)
    for i in range(2*N):
        C[i+1] = C[i] + A[i % N]
    diff = C[N]  # S の合計
    
    # 全体の不均衡修正は常に |diff|/2
    cost_imbalance = abs(diff) // 2

    # スライディングウィンドウ（区間サイズ = N+1）で C[r...r+N] の最小値を求める
    # ここでは r=0,...,N-1 について求める
    window_size = N + 1
    deq = deque()
    min_in_window = [0]*(2*N+1)
    
    # 最初のウィンドウ：インデックス 0 から window_size-1
    for i in range(window_size):
        while deq and C[deq[-1]] >= C[i]:
            deq.pop()
        deq.append(i)
    min_in_window[0] = C[deq[0]]
    
    # i はウィンドウの左端 (r)
    # ウィンドウは [i, i+N]
    for r in range(1, N):
        # deq の先頭がウィンドウ外なら pop する
        while deq and deq[0] < r:
            deq.popleft()
        # 新しくウィンドウに入る要素のインデックス: r+N
        new_index = r + N
        while deq and C[deq[-1]] >= C[new_index]:
            deq.pop()
        deq.append(new_index)
        min_in_window[r] = C[deq[0]]
    
    # 各回転 r に対して候補コストを計算
    # cost(r) = cost_imbalance + max(0, C[r] - (min_{j in [r, r+N]} C[j]))
    best = float('inf')
    for r in range(N):
        candidate = cost_imbalance + max(0, C[r] - min_in_window[r])
        best = min(best, candidate)
    
    print(best)


if __name__ == '__main__':
    solve()
0