結果

問題 No.265 数学のテスト
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:49:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,381 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 150,520 KB
最終ジャッジ日時 2025-03-20 18:50:50
合計ジャッジ時間 8,816 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    d_input = int(input[1])
    S = input[2]

    def expand_derivatives(s, d):
        while True:
            pos = s.find('d{')
            if pos == -1:
                break
            stack = 1
            end_pos = pos + 2
            for i in range(pos + 2, len(s)):
                if s[i] == '{':
                    stack += 1
                elif s[i] == '}':
                    stack -= 1
                    if stack == 0:
                        end_pos = i
                        break
            else:
                break
            T = s[pos+2:end_pos]
            expanded_T = expand_derivatives(T, d)
            poly_T = parse_expression(expanded_T, d)
            derived_poly = derive_polynomial(poly_T, d)
            derived_expr = polynomial_to_expression(derived_poly, d)
            s = s[:pos] + derived_expr + s[end_pos+1:]
        return s

    def parse_expression(s, d):
        pos = 0
        n = len(s)
        
        def add_polynomials(a, b):
            max_len = max(len(a), len(b))
            a_ext = a + [0]*(max_len - len(a))
            b_ext = b + [0]*(max_len - len(b))
            res = [a_ext[i] + b_ext[i] for i in range(max_len)]
            return res[:d+1]
        
        def multiply_polynomials(a, b):
            res = [0]*(d+1)
            for i in range(min(len(a), d+1)):
                if a[i] == 0:
                    continue
                for j in range(min(len(b), d+1)):
                    if b[j] == 0:
                        continue
                    k = i + j
                    if k <= d:
                        res[k] += a[i] * b[j]
            return res
        
        def skip_whitespace():
            nonlocal pos
            while pos < n and s[pos] in ' \t':
                pos += 1
        
        def parse_expr():
            nonlocal pos
            skip_whitespace()
            poly = parse_term()
            skip_whitespace()
            while pos < n and s[pos] == '+':
                pos += 1
                skip_whitespace()
                term_poly = parse_term()
                poly = add_polynomials(poly, term_poly)
                skip_whitespace()
            return poly
        
        def parse_term():
            nonlocal pos
            skip_whitespace()
            poly = parse_factor()
            skip_whitespace()
            while pos < n and s[pos] == '*':
                pos += 1
                skip_whitespace()
                factor_poly = parse_factor()
                poly = multiply_polynomials(poly, factor_poly)
                skip_whitespace()
            return poly
        
        def parse_factor():
            nonlocal pos
            skip_whitespace()
            sign = 1
            if pos < n and s[pos] == '-':
                sign = -1
                pos += 1
                skip_whitespace()
            if pos >= n:
                return [0]*(d+1)
            if s[pos] == 'x':
                pos += 1
                return create_x_poly(sign, d)
            elif s[pos].isdigit():
                num = int(s[pos])
                pos += 1
                while pos < n and s[pos].isdigit():
                    num = num * 10 + int(s[pos])
                    pos += 1
                coeff = sign * num
                return create_constant_poly(coeff, d)
            else:
                raise ValueError(f"Unexpected character at {pos}: {s[pos]}")
        
        def create_constant_poly(coeff, d):
            poly = [0]*(d+1)
            poly[0] = coeff
            return poly
        
        def create_x_poly(sign, d):
            poly = [0]*(d+1)
            if d >= 1:
                poly[1] = sign
            return poly
        
        try:
            return parse_expr()
        except:
            return [0]*(d+1)
    
    def derive_polynomial(poly, d):
        derived = [0]*(d+1)
        for i in range(d+1):
            if i + 1 < len(poly):
                derived[i] = (i + 1) * poly[i + 1]
            else:
                derived[i] = 0
        return derived
    
    def polynomial_to_expression(poly, d):
        terms = []
        for exp in range(d+1):
            coeff = poly[exp]
            if coeff == 0:
                continue
            term = []
            if coeff < 0:
                term.append('-')
                abs_coeff = -coeff
            else:
                abs_coeff = coeff
            if exp == 0:
                term.append(str(abs_coeff))
            else:
                x_parts = ['x'] * exp
                x_str = '*'.join(x_parts)
                if abs_coeff != 1 or len(x_parts) == 0:
                    term.append(str(abs_coeff))
                    if len(x_parts) > 0:
                        term.append('*')
                        term.append(x_str)
                else:
                    term.append(x_str)
            terms.append(''.join(term))
        if not terms:
            return '0'
        expr = '+'.join(terms)
        expr = expr.replace('+-', '-')
        return expr
    
    expanded_S = expand_derivatives(S, d_input)
    final_poly = parse_expression(expanded_S, d_input)
    final_poly = final_poly[:d_input+1]
    output = ' '.join(map(str, final_poly))
    print(output)

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