結果

問題 No.2106 Wild Cacco
ユーザー lam6er
提出日時 2025-03-20 20:48:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,081 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 277,376 KB
最終ジャッジ日時 2025-03-20 20:49:03
合計ジャッジ時間 4,513 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    # Initialize DP: { (low, high, parity): count }
    dp = {}
    dp[(0, 0, 0)] = 1

    for i in range(n):
        char = s[i]
        new_dp = {}
        for (l_prev, h_prev, p_prev), cnt in dp.items():
            choices = []
            if char == '.':
                choices = ['(', ')', '?']
            else:
                choices = [char]
            
            for c in choices:
                delta_l, delta_h = 0, 0
                if c == '(':
                    delta_l = 1
                    delta_h = 1
                elif c == ')':
                    delta_l = -1
                    delta_h = -1
                else:  # '?'
                    delta_l = -1
                    delta_h = 1
                
                new_l_raw = l_prev + delta_l
                new_h_raw = h_prev + delta_h
                new_l = max(new_l_raw, 0)
                new_h = new_h_raw
                if new_h < 0:
                    continue

                # Compute new_p
                new_p = (p_prev + 1) % 2  # since any c toggles the parity

                key = (new_l, new_h, new_p)
                if key in new_dp:
                    new_dp[key] = (new_dp[key] + cnt) % MOD
                else:
                    new_dp[key] = cnt % MOD
        
        # Merge intervals for each parity
        merged = {}
        for (l, h, p), cnt in new_dp.items():
            # Merge is done by replacing with the widest interval and same p
            # Since merging might not reduce the states, this is a placeholder
            merged_key = (l, h, p)
            if merged_key in merged:
                merged[merged_key] = (merged[merged_key] + cnt) % MOD
            else:
                merged[merged_key] = cnt % MOD
        dp = merged

    total = 0
    for (l, h, p) in dp:
        if l <= 0 <= h and p == 0:
            total = (total + dp[(l, h, p)]) % MOD
    print(total % MOD)

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