結果

問題 No.2106 Wild Cacco
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:46:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,946 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 77,340 KB
最終ジャッジ日時 2025-06-12 20:46:40
合計ジャッジ時間 5,260 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

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

if n % 2 != 0:
    print(0)
    exit()

from collections import defaultdict

# DP structure: dp[has_q][min_balance][max_balance] = count
# where has_q is 0 (no '?') or 1 (has '?')
dp = [defaultdict(int) for _ in range(2)]
dp[0][(0, 0)] = 1  # Initial state: has_q=0, min=0, max=0

for c in s:
    next_dp = [defaultdict(int) for _ in range(2)]
    for has_q in [0, 1]:
        for (min_b, max_b), cnt in dp[has_q].items():
            replacements = []
            if c == '.':
                replacements = ['(', ')', '?']
            else:
                replacements = [c]
            for r in replacements:
                new_has_q = has_q or (r == '?')
                if r == '(':
                    new_min = min_b + 1
                    new_max = max_b + 1
                elif r == ')':
                    new_min = min_b - 1
                    new_max = max_b - 1
                else:  # r == '?'
                    new_min = min_b - 1
                    new_max = max_b + 1
                new_min = max(new_min, 0)
                if new_max < 0:
                    continue
                if new_has_q:
                    next_dp[1][(new_min, new_max)] = (next_dp[1][(new_min, new_max)] + cnt) % MOD
                else:
                    if new_min == new_max:
                        next_dp[0][(new_min, new_max)] = (next_dp[0][(new_min, new_max)] + cnt) % MOD
    # Merge overlapping intervals for has_q=1
    merged = defaultdict(int)
    for (min_b, max_b), cnt in next_dp[1].items():
        key = (min_b, max_b)
        merged[key] = (merged[key] + cnt) % MOD
    next_dp[1] = merged
    dp = next_dp

ans = 0
# Check for has_q=1 where 0 is within [min, max]
for (min_b, max_b), cnt in dp[1].items():
    if min_b <= 0 <= max_b:
        ans = (ans + cnt) % MOD
# Check for has_q=0 where balance is exactly 0
ans = (ans + dp[0].get((0, 0), 0)) % MOD

print(ans)
0