結果

問題 No.1677 mæx
ユーザー brthyyjpbrthyyjp
提出日時 2021-09-11 03:18:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 1,020 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 87,000 KB
実行使用メモリ 134,852 KB
最終ジャッジ日時 2023-09-03 23:27:34
合計ジャッジ時間 6,767 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,272 KB
testcase_01 AC 70 ms
70,996 KB
testcase_02 AC 72 ms
70,984 KB
testcase_03 AC 75 ms
71,268 KB
testcase_04 AC 293 ms
117,004 KB
testcase_05 AC 298 ms
118,840 KB
testcase_06 AC 299 ms
117,540 KB
testcase_07 AC 292 ms
117,896 KB
testcase_08 AC 293 ms
117,352 KB
testcase_09 AC 296 ms
118,672 KB
testcase_10 AC 294 ms
116,264 KB
testcase_11 AC 286 ms
118,112 KB
testcase_12 AC 288 ms
117,320 KB
testcase_13 AC 292 ms
116,648 KB
testcase_14 AC 279 ms
115,792 KB
testcase_15 AC 286 ms
117,624 KB
testcase_16 AC 282 ms
115,276 KB
testcase_17 AC 280 ms
115,792 KB
testcase_18 AC 286 ms
116,952 KB
testcase_19 AC 72 ms
71,244 KB
testcase_20 AC 72 ms
71,388 KB
testcase_21 AC 299 ms
134,852 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