結果

問題 No.2106 Wild Cacco
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:47:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,535 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 275,028 KB
最終ジャッジ日時 2025-06-12 20:49:34
合計ジャッジ時間 4,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

# Initialize DP with initial state (min_balance=0, max_balance=0) and count 1
dp = defaultdict(int)
dp[(0, 0)] = 1

for char in s:
    new_dp = defaultdict(int)
    for (a, b), cnt in dp.items():
        if char == '.':
            # Replace '.' with '(', ')', or '?'
            # Each choice contributes to the transitions
            for delta_a, delta_b in [(1, 1), (-1, -1), (-1, 1)]:
                new_a = a + delta_a
                new_b = b + delta_b
                new_a_clamped = max(new_a, 0)
                if new_b < new_a_clamped:
                    continue  # Invalid state
                new_dp[(new_a_clamped, new_b)] = (new_dp[(new_a_clamped, new_b)] + cnt) % MOD
        else:
            # Process the fixed character
            if char == '(':
                delta_a, delta_b = 1, 1
            elif char == ')':
                delta_a, delta_b = -1, -1
            else:  # char is '?'
                delta_a, delta_b = -1, 1
            new_a = a + delta_a
            new_b = b + delta_b
            new_a_clamped = max(new_a, 0)
            if new_b < new_a_clamped:
                continue  # Invalid state
            new_dp[(new_a_clamped, new_b)] = (new_dp[(new_a_clamped, new_b)] + cnt) % MOD
    dp = new_dp

# Check if any state allows the final balance to be 0
ans = 0
for (a, b), cnt in dp.items():
    if a <= 0 <= b:
        ans = (ans + cnt) % MOD

print(ans)
0