結果
問題 |
No.2031 Colored Brackets
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:47:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 439 ms / 2,000 ms |
コード長 | 2,532 bytes |
コンパイル時間 | 145 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 160,740 KB |
最終ジャッジ日時 | 2025-03-20 18:48:22 |
合計ジャッジ時間 | 5,070 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
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)