結果

問題 No.265 数学のテスト
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:37:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,489 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 110,080 KB
最終ジャッジ日時 2025-06-12 21:40:35
合計ジャッジ時間 5,131 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def tokenize(s):
    i = 0
    while i < len(s):
        if s[i] in '+-*{}()':
            yield s[i]
            i += 1
        elif s[i] == 'd':
            if i + 1 < len(s) and s[i + 1] == '{':
                j = i + 2
                depth = 1
                while j < len(s) and depth > 0:
                    if s[j] == '{':
                        depth += 1
                    elif s[j] == '}':
                        depth -= 1
                    j += 1
                expr = s[i + 2:j - 1]
                yield ('d', expr)
                i = j
            else:
                yield 'd'
                i += 1
        elif s[i] == 'x':
            yield 'x'
            i += 1
        elif s[i].isdigit():
            j = i + 1
            while j < len(s) and s[j].isdigit():
                j += 1
            num = int(s[i:j])
            yield ('const', num)
            i = j
        else:
            raise ValueError("Invalid character: " + s[i])
            i += 1

def poly_add(a, b):
    max_len = max(len(a), len(b))
    result = [0] * max_len
    for i in range(max_len):
        if i < len(a):
            result[i] += a[i]
        if i < len(b):
            result[i] += b[i]
    return result

def poly_mul(a, b):
    len_a = len(a)
    len_b = len(b)
    result = [0] * (len_a + len_b - 1)
    for i in range(len_a):
        for j in range(len_b):
            result[i + j] += a[i] * b[j]
    return result

def poly_derivative(p):
    if len(p) == 0:
        return []
    deriv = []
    for i in range(1, len(p)):
        deriv.append(i * p[i])
    return deriv

def parse_expression(tokens, current):
    poly, current = parse_term(tokens, current)
    while current < len(tokens) and tokens[current] == '+':
        current += 1
        term, current = parse_term(tokens, current)
        poly = poly_add(poly, term)
    return poly, current

def parse_term(tokens, current):
    poly, current = parse_factor(tokens, current)
    while current < len(tokens) and tokens[current] == '*':
        current += 1
        factor, current = parse_factor(tokens, current)
        poly = poly_mul(poly, factor)
    return poly, current

def parse_factor(tokens, current):
    token = tokens[current]
    if token == 'x':
        current += 1
        return [0, 1], current
    elif isinstance(token, tuple) and token[0] == 'd':
        expr_str = token[1]
        expr_tokens = list(tokenize(expr_str))
        expr_poly, _ = parse_expression(expr_tokens, 0)
        current += 1
        deriv_poly = poly_derivative(expr_poly)
        return deriv_poly, current
    elif isinstance(token, tuple) and token[0] == 'const':
        const = token[1]
        current += 1
        return [const], current
    elif token == '(':
        current += 1
        expr_poly, current = parse_expression(tokens, current)
        if current >= len(tokens) or tokens[current] != ')':
            raise ValueError("Expected ')'")
        current += 1
        return expr_poly, current
    else:
        raise ValueError("Unexpected token: " + str(token))

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    d = int(input[1])
    S = input[2]
    tokens = list(tokenize(S))
    poly, _ = parse_expression(tokens, 0)
    max_degree = d
    result = [0] * (max_degree + 1)
    for i in range(len(poly)):
        if i <= max_degree:
            result[i] = poly[i]
    print(' '.join(map(str, result)))

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