結果

問題 No.2031 Colored Brackets
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:32:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 432 ms / 2,000 ms
コード長 2,532 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,744 KB
実行使用メモリ 160,568 KB
最終ジャッジ日時 2025-03-20 20:33:13
合計ジャッジ時間 5,027 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n = int(input())
s = input().strip()

# Compute d array, d[i] is the cumulative balance after first i characters
d = [0] * (n + 1)
for i in range(n):
    d[i+1] = d[i] + (1 if s[i] == '(' else -1)

# Initialize DP table
dp = [{} for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    current_char = s[i]
    current_d_prev = d[i]
    next_d = d[i+1]
    
    for x_prev in list(dp[i].keys()):
        count = dp[i][x_prev]
        
        if current_char == '(':
            # Red case: add to red, x increases by 1
            x_new = x_prev + 1
            y_new = current_d_prev - x_prev  # y_prev = d[i] - x_prev, not changed since this is a red ( and not affecting blue
            new_d = current_d_prev + 1
            if x_new <= new_d and y_new >= 0:
                if x_new in dp[i+1]:
                    dp[i+1][x_new] = (dp[i+1][x_new] + count) % MOD
                else:
                    dp[i+1][x_new] = count % MOD
            
            # Blue case: add to blue, x remains, blue y increases by 1
            x_new_blue = x_prev
            y_prev_blue = current_d_prev - x_prev
            y_new_blue = y_prev_blue + 1
            if x_new_blue <= new_d and y_new_blue <= new_d - x_new_blue:
                if x_new_blue in dp[i+1]:
                    dp[i+1][x_new_blue] = (dp[i+1][x_new_blue] + count) % MOD
                else:
                    dp[i+1][x_new_blue] = count % MOD
        else:
            # current_char is ')', Red case: subtract 1 from x_prev
            if x_prev >= 1:
                x_new_red = x_prev - 1
                new_d_red = current_d_prev - 1
                y_new_red = new_d_red - x_new_red
                if x_new_red >= 0 and y_new_red >= 0:
                    if x_new_red in dp[i+1]:
                        dp[i+1][x_new_red] = (dp[i+1][x_new_red] + count) % MOD
                    else:
                        dp[i+1][x_new_red] = count % MOD
            
            # Blue case: subtract 1 from y_prev
            y_prev_blue = current_d_prev - x_prev
            if y_prev_blue >= 1:
                x_new_blue = x_prev
                y_new_blue_after = y_prev_blue - 1
                new_d_blue = current_d_prev - 1
                if y_new_blue_after >= 0 and x_new_blue <= new_d_blue:
                    if x_new_blue in dp[i+1]:
                        dp[i+1][x_new_blue] = (dp[i+1][x_new_blue] + count) % MOD
                    else:
                        dp[i+1][x_new_blue] = count % MOD

print(dp[n].get(0, 0) % MOD)
0