結果

問題 No.1677 mæx
ユーザー brthyyjpbrthyyjp
提出日時 2021-09-11 03:18:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 317 ms / 2,000 ms
コード長 1,020 bytes
コンパイル時間 694 ms
コンパイル使用メモリ 81,728 KB
実行使用メモリ 132,376 KB
最終ジャッジ日時 2024-06-13 04:00:10
合計ジャッジ時間 6,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,068 KB
testcase_01 AC 38 ms
53,208 KB
testcase_02 AC 37 ms
52,568 KB
testcase_03 AC 37 ms
52,620 KB
testcase_04 AC 317 ms
114,988 KB
testcase_05 AC 259 ms
117,312 KB
testcase_06 AC 289 ms
115,660 KB
testcase_07 AC 261 ms
115,644 KB
testcase_08 AC 249 ms
114,508 KB
testcase_09 AC 254 ms
117,224 KB
testcase_10 AC 255 ms
115,404 KB
testcase_11 AC 254 ms
116,148 KB
testcase_12 AC 246 ms
114,144 KB
testcase_13 AC 251 ms
115,592 KB
testcase_14 AC 247 ms
114,104 KB
testcase_15 AC 265 ms
114,984 KB
testcase_16 AC 240 ms
114,636 KB
testcase_17 AC 232 ms
114,520 KB
testcase_18 AC 259 ms
115,428 KB
testcase_19 AC 35 ms
53,500 KB
testcase_20 AC 35 ms
52,680 KB
testcase_21 AC 270 ms
132,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**9)

s = str(input())
k = int(input())
mod = 998244353
n = len(s)

def mex(a, b):
    for i in range(3):
        if i not in (a, b):
            return i

nx = [-1]*n
stack = []
for i, c in enumerate(s):
    if c == '(':
        stack.append(i)
    elif c == ',':
        nx[stack[-1]] = i
    elif c == ')':
        stack.pop()

def rec(l, r):
    # [l, r)
    if l+1 == r:
        if s[l] == '?':
            return [1]*3
        res = [0]*3
        res[int(s[l])] = 1
        return res

    r -= 1
    l += 1
    ops = []
    if s[l] == '?':
        ops.append(max)
        ops.append(mex)
    elif s[l] == 'a':
        ops.append(max)
    elif s[l] == 'e':
        ops.append(mex)
    l += 2

    m = nx[l]
    A = rec(l+1, m)
    B = rec(m+1, r)
    res = [0]*3
    for op in ops:
        for i, a in enumerate(A):
            for j, b in enumerate(B):
                x = op(i, j)
                res[x] += a*b
                res[x] %= mod
    return res

print(rec(0, n)[k])
0