結果

問題 No.1677 mæx
ユーザー lam6er
提出日時 2025-04-16 15:49:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,794 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,004 KB
実行使用メモリ 88,248 KB
最終ジャッジ日時 2025-04-16 15:51:29
合計ジャッジ時間 3,961 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def precompute_paren_map(s):
    stack = []
    paren_map = {}
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            if stack:
                opening = stack.pop()
                paren_map[opening] = i
    return paren_map

def find_comma(s, start, end):
    depth = 0
    for i in range(start, end + 1):
        c = s[i]
        if c == '(':
            depth += 1
        elif c == ')':
            depth -= 1
        elif c == ',' and depth == 0:
            return i
    return -1

def main():
    s = input().strip()
    K = int(input())
    n = len(s)
    if n == 0:
        print(0)
        return
    
    paren_map = precompute_paren_map(s)
    
    stack = [(0, n-1, None)]
    processed = []
    
    while stack:
        start, end, state = stack.pop()
        if state is None:
            if start > end:
                continue
            if s[start] in '012?':
                # Digit node
                if s[start] == '?':
                    dp = [1, 1, 1]
                else:
                    val = int(s[start])
                    dp = [0] * 3
                    dp[val] = 1
                processed.append(('digit', dp))
            else:
                # Function call
                func_start = start
                while func_start <= end and s[func_start] != '(':
                    func_start += 1
                func_name_part = s[start:func_start]
                possible_funcs = []
                for f in ['max', 'mex']:
                    valid = True
                    for k in range(3):
                        c = func_name_part[k] if k < len(func_name_part) else '?'
                        if c != '?' and c != f[k]:
                            valid = False
                            break
                    if valid:
                        possible_funcs.append((f, 1))
                opening = func_start
                if opening not in paren_map:
                    processed.append(('function', [0, 0, 0]))
                    continue
                closing = paren_map[opening]
                comma_pos = find_comma(s, opening + 1, closing - 1)
                if comma_pos == -1:
                    processed.append(('function', [0, 0, 0]))
                    continue
                stack.append((start, end, ('function', possible_funcs, opening, closing, comma_pos)))
                stack.append((comma_pos + 1, closing - 1, None))
                stack.append((opening + 1, comma_pos - 1, None))
        else:
            # Process function node
            possible_funcs, opening, closing, comma_pos = state[1:]
            arg2 = processed.pop()[1]
            arg1 = processed.pop()[1]
            dp = [0] * 3
            for (f_type, f_count) in possible_funcs:
                combined = [0] * 3
                for a in range(3):
                    for b in range(3):
                        if arg1[a] == 0 or arg2[b] == 0:
                            continue
                        if f_type == 'max':
                            res = max(a, b)
                        else:
                            mex_val = 0
                            while mex_val == a or mex_val == b:
                                mex_val += 1
                            res = mex_val if mex_val <= 2 else 2
                        if res <= 2:
                            combined[res] = (combined[res] + arg1[a] * arg2[b]) % MOD
                for i in range(3):
                    dp[i] = (dp[i] + f_count * combined[i]) % MOD
            processed.append(('function', dp))
    
    if not processed:
        print(0)
    else:
        result = processed[0][1][K] % MOD
        print(result)

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