結果

問題 No.2106 Wild Cacco
ユーザー lam6er
提出日時 2025-04-15 21:09:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,400 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 288,140 KB
最終ジャッジ日時 2025-04-15 21:15:37
合計ジャッジ時間 4,702 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    s = input().strip()
    n = len(s)
    if n % 2 != 0:
        print(0)
        return
    
    target = n // 2
    # dp is a dictionary where keys are tuples (lo, hi, a, c) and values are counts
    dp = {}
    dp[(0, 0, 0, 0)] = 1  # initial state: position 0, lo=0, hi=0, a=0, c=0
    
    for i in range(n):
        char = s[i]
        new_dp = {}
        for state in dp:
            current_lo, current_hi, current_a, current_c = state
            count = dp[state]
            
            if char != '.':
                # Process fixed character
                if char == '(':
                    new_a = current_a + 1
                    new_c = current_c
                    new_lo = current_lo + 1
                    new_hi = current_hi + 1
                elif char == ')':
                    new_a = current_a
                    new_c = current_c
                    new_lo = current_lo - 1
                    new_hi = current_hi - 1
                else:  # char == '?'
                    new_a = current_a
                    new_c = current_c + 1
                    new_lo = current_lo - 1
                    new_hi = current_hi + 1
                
                new_lo_clamped = max(new_lo, 0)
                if new_hi < 0:
                    continue
                key = (new_lo_clamped, new_hi, new_a, new_c)
                if key in new_dp:
                    new_dp[key] = (new_dp[key] + count) % MOD
                else:
                    new_dp[key] = count % MOD
            else:
                # Replace with '('
                new_a = current_a + 1
                new_c = current_c
                new_lo = current_lo + 1
                new_hi = current_hi + 1
                new_lo_clamped = max(new_lo, 0)
                if new_hi >= 0:
                    key = (new_lo_clamped, new_hi, new_a, new_c)
                    if key in new_dp:
                        new_dp[key] = (new_dp[key] + count) % MOD
                    else:
                        new_dp[key] = count % MOD
                
                # Replace with ')'
                new_a = current_a
                new_c = current_c
                new_lo = current_lo - 1
                new_hi = current_hi - 1
                new_lo_clamped = max(new_lo, 0)
                if new_hi >= 0:
                    key = (new_lo_clamped, new_hi, new_a, new_c)
                    if key in new_dp:
                        new_dp[key] = (new_dp[key] + count) % MOD
                    else:
                        new_dp[key] = count % MOD
                
                # Replace with '?'
                new_a = current_a
                new_c = current_c + 1
                new_lo = current_lo - 1
                new_hi = current_hi + 1
                new_lo_clamped = max(new_lo, 0)
                if new_hi >= 0:
                    key = (new_lo_clamped, new_hi, new_a, new_c)
                    if key in new_dp:
                        new_dp[key] = (new_dp[key] + count) % MOD
                    else:
                        new_dp[key] = count % MOD
        dp = new_dp
    
    total = 0
    for state in dp:
        lo, hi, a, c = state
        if lo <= 0 <= hi:
            if a <= target and (a + c) >= target:
                total = (total + dp[state]) % MOD
    print(total % MOD)

if __name__ == "__main__":
    main()
0