結果

問題 No.265 数学のテスト
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:38:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,519 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 287,840 KB
最終ジャッジ日時 2025-06-12 21:41:25
合計ジャッジ時間 6,583 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find_matching_brace(s, pos):
    stack = []
    for i in range(pos, len(s)):
        if s[i] == '{':
            stack.append(i)
        elif s[i] == '}':
            if stack:
                start = stack.pop()
                if not stack:
                    return (start, i)
    return None

def extract_plus_terms(s):
    terms = []
    stack = []
    current = []
    i = 0
    while i < len(s):
        c = s[i]
        if c == '+':
            if not stack:
                terms.append(''.join(current))
                current = []
            else:
                current.append(c)
        elif c == '{':
            stack.append('{')
            current.append(c)
        elif c == '}':
            stack.pop()
            current.append(c)
        else:
            current.append(c)
        i += 1
    if current:
        terms.append(''.join(current))
    return terms

def compute_derivative(p):
    dp = [0] * (len(p) - 1)
    for i in range(1, len(p)):
        dp[i - 1] = p[i] * i
    return dp

def add_polynomials(a, b, d_max):
    result = [0] * (d_max + 1)
    for i in range(d_max + 1):
        if i < len(a):
            result[i] += a[i]
        if i < len(b):
            result[i] += b[i]
    return result

def multiply_polynomials(a, b, d_max):
    result = [0] * (d_max + 1)
    for i in range(len(a)):
        if a[i] == 0:
            continue
        for j in range(len(b)):
            if b[j] == 0:
                continue
            if i + j > d_max:
                continue
            result[i + j] += a[i] * b[j]
    return result

def parse(s, d_max):
    terms = extract_plus_terms(s)
    result = [0] * (d_max + 1)
    for term in terms:
        if term.startswith('d{'):
            start = term.find('{')
            end = find_matching_brace(term, start)[1]
            t = term[start+1 : end]
            p = parse(t, d_max + 1)
            dp = compute_derivative(p)
            if len(dp) > d_max + 1:
                dp = dp[:d_max + 1]
            else:
                dp += [0] * (d_max + 1 - len(dp))
            for i in range(d_max + 1):
                result[i] += dp[i]
        else:
            factors = term.split('*')
            poly = [0] * (d_max + 1)
            poly[0] = 1
            for factor in factors:
                if factor == 'x':
                    f_poly = [0] * (d_max + 1)
                    f_poly[1] = 1
                elif factor.isdigit():
                    f_poly = [0] * (d_max + 1)
                    f_poly[0] = int(factor)
                else:
                    f_poly = [0] * (d_max + 1)
                new_poly = [0] * (d_max + 1)
                for i in range(d_max + 1):
                    if poly[i] == 0:
                        continue
                    for j in range(d_max + 1):
                        if f_poly[j] == 0:
                            continue
                        if i + j > d_max:
                            continue
                        new_poly[i + j] += poly[i] * f_poly[j]
                poly = new_poly
            for i in range(d_max + 1):
                result[i] += poly[i]
    return result

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    d = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    result_poly = parse(S, d)
    output = []
    for i in range(d + 1):
        output.append(str(result_poly[i]))
    print(' '.join(output))

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