概要

ポーランド記法（前置記法）で書かれた数式を評価する問題です。元の数式と、指定された位置の演算子を対になる演算子に置き換えた数式の両方の評価結果を求めます。

考察

ポーランド記法の評価方法

ポーランド記法の数式はトークンを左から右に読みながらスタックを使って評価できます。通常の逆ポーランド記法（後置記法）ではトークンを読んでスタックに積み、演算子が来たらスタックから2つ取り出して計算しますが、前置記法では演算子が先に来るため、少し工夫が必要です。

重要な気づき

1. 2つの数式を同時に評価できる: 元の数式と反転後の数式は構造（木の形）が完全に同じで、演算子だけが異なります。したがって、1回のパースで両方を同時に評価できます。

2. スタックベースの評価: 前置記法を左から右に読む際、演算子に出会ったら「オペランドを待っている状態」としてスタックに積み、数値に出会ったらスタックの状態に応じて計算を進めます。

スタックの状態管理

スタック上の各エントリは以下の3種類です：

• val: 評価済みの値（元の値、反転後の値のペア）
• op1: 演算子を読んだが、まだ第1オペランドを受け取っていない状態
• op2: 第1オペランドまで確定し、第2オペランドを待っている状態

例として * + 3 5 2 の処理を追います：

読むトークン	スタックの遷移
*	[op1: *]
+	[op1: *, op1: +]
3	3 は値 → op1: + と合体 → [op1: *, op2: +(3)]
5	5 は値 → op2: +(3) と合体 → 3+5=8 が値に → op1: * と合体 → [op2: *(8)]
2	2 は値 → op2: *(8) と合体 → 8*2=16 が値 → [val: 16]

最終結果は \(16\) です。

除算の注意

/ は 0 に向かって切り捨てる整数除算です。Python の // は床除算（負の無限大方向への切り捨て）なので、符号が異なる場合に結果が変わります。例えば \((-7) / 2\) は \(-3\)（0方向）ですが、Python の (-7) // 2 は \(-4\)（床方向）です。これを正しく処理する必要があります。

アルゴリズム

1. 入力を読み、反転対象の位置を集合に格納する。
2. トークンを左から右に順に処理する：
   • 演算子の場合: 元の演算子と反転後の演算子を記録し、op1 としてスタックに積む。
   • 数値の場合: 値を val として作り、スタックトップが op2（第2オペランドを待っている）なら計算して結合。結合後の結果がさらに op2 を解消できるなら繰り返す。最後にスタックトップが op1 なら op2 に昇格させる。
3. 最終的にスタックに残った1つの val が答え。

計算量

• 時間計算量: \(O(N)\) — 各トークンは定数回のスタック操作で処理される
• 空間計算量: \(O(N)\) — スタックと反転位置の集合に \(O(N)\)

実装のポイント

• truncated division の実装: Python の // は床除算なので、被除数と除数の符号が異なるとき結果がずれます。(a ^ b) >= 0 で同符号かを判定し、異符号の場合は絶対値で割ってから符号を付けます。

• スタックの縮約ループ: 数値を読んだ後、スタックトップの op2 と連鎖的に結合できるので while ループで処理します。これにより + 1 + 2 + 3 4 のようなネストした式も正しく評価されます。

• -0 の非存在: 問題の制約で -0 は与えられないため、トークンが - の1文字なら必ず演算子と判定して安全です。

  ソースコード

import sys
from typing import List, Tuple

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens_input = input_data.split()
    idx = 0
    N = int(tokens_input[idx]); idx += 1
    toks = tokens_input[idx:idx+N]; idx += N
    K = int(tokens_input[idx]); idx += 1
    
    flipped = set()
    if K > 0:
        for i in range(K):
            p = int(tokens_input[idx]); idx += 1
            flipped.add(p - 1)  # 0-indexed
    
    def flip_op(op):
        if op == '+': return '-'
        if op == '-': return '+'
        if op == '*': return '/'
        if op == '/': return '*'
    
    def is_operator(t):
        return t in ('+', '-', '*', '/')
    
    # Build the expression tree iteratively using a stack-based approach
    # We'll evaluate both original and flipped expressions simultaneously
    
    # First, let's parse the Polish notation into a tree structure
    # Then evaluate both versions
    
    # For efficiency, we do iterative evaluation using a stack
    # We process tokens left to right. 
    # Stack contains entries: either a resolved value or a partially applied operator
    
    # Each stack entry: (type, ...)
    # type 'val': ('val', original_value, flipped_value)
    # type 'op1': waiting for first operand - ('op1', orig_op, flip_op)
    # type 'op2': has first operand, waiting for second - ('op2', orig_op, flip_op, orig_val1, flip_val1)
    
    def trunc_div(a, b):
        # Truncated division toward zero
        if b == 0:
            raise ZeroDivisionError
        # Python's // is floor division, we need truncation toward zero
        if (a ^ b) >= 0:
            return a // b
        else:
            return -((-a) // b) if a < 0 else -(a // (-b))
    
    def apply_op(op, a, b):
        if op == '+': return a + b
        if op == '-': return a - b
        if op == '*': return a * b
        if op == '/': return trunc_div(a, b)
    
    stack = []
    
    for i in range(N):
        t = toks[i]
        if is_operator(t):
            orig_op = t
            if i in flipped:
                flip = flip_op(t)
            else:
                flip = t
            stack.append(('op1', orig_op, flip))
        else:
            # It's a number
            val = int(t)
            # Try to reduce
            current = ('val', val, val)
            
            while stack and stack[-1][0] == 'op2':
                entry = stack.pop()
                _, orig_op, flip, ov1, fv1 = entry
                ov2 = current[1]
                fv2 = current[2]
                orig_res = apply_op(orig_op, ov1, ov2)
                flip_res = apply_op(flip, fv1, fv2)
                current = ('val', orig_res, flip_res)
            
            if stack and stack[-1][0] == 'op1':
                entry = stack.pop()
                _, orig_op, flip = entry
                stack.append(('op2', orig_op, flip, current[1], current[2]))
            else:
                stack.append(current)
    
    # The stack should have exactly one 'val' entry
    result = stack[0]
    print(result[1])
    print(result[2])

solve()

---

この解説は claude4.6opus-thinking によって生成されました。