概要

ポーランド記法（前置記法）で書かれた数式について、指定された位置の演算子を反転（+↔-、*↔/）した前後の評価結果を求める問題です。

考察

ポーランド記法の数式を評価する基本的な方法は、トークンを後ろから順に処理してスタックを用いる方法です。この問題では、元の数式と演算子を反転させた数式の両方を評価する必要があります。

素朴なアプローチでは、元のトークン列と反転後のトークン列の両方に対して独立に評価処理を行うことが考えられます。しかし、各評価処理はトークン数 \(N\) に対して \(O(N)\) 時間かかるため、全体として \(O(N)\) 時間で実行可能です。制約条件では \(N \leq 2 \times 10^5\) なので、このアプローチで十分高速です。

注意点として、除算 / は0に向かって切り捨てる整数除算であるため、通常のPythonの整数除算 (//) とは挙動が異なります。特に、負の数を含む除算では正しい結果を得るために特別な処理が必要です。

アルゴリズム

1. 入力からトークン列と反転位置を読み取る
2. 元のトークン列のコピーを作成し、指定された位置の演算子を反転させたトークン列を作成する
3. 両方のトークン列に対して以下の評価処理を行う：
   • トークン列を後ろから順に処理する
   • 演算子の場合はスタックから2つの値を取り出し、演算結果をスタックに積む
   • 整数の場合はその値をスタックに積む
4. スタックに残った最終結果を出力する

除算処理では、以下のように0に向かって切り捨てる処理を実装します： - 被除数と除数の符号が異なる場合は結果が負になる - 絶対値の除算を行い、符号を調整する

計算量

• 時間計算量: \(O(N)\)
  • トークン列のコピー: \(O(N)\)
  • 演算子の反転処理: \(O(K)\)
  • 評価処理（2回）: 各 \(O(N)\)
• 空間計算量: \(O(N)\)
  • トークン列の保存: \(O(N)\)
  • 評価用スタック: \(O(N)\)

実装のポイント

• 除算処理の実装：通常の整数除算 (//) は負の無限大方向への切り捨てを行うため、問題で要求される0方向への切り捨てとは異なります。符号を別途管理して絶対値で除算を行う必要があります。

• トークンの処理順序：ポーランド記法は前置記法なので、後ろから処理すると自然に評価できます。

• 反転位置の管理：\(1\)-indexedで与えられるため、\(0\)-indexedに変換する必要があります。

• ゼロ除算の回避：問題制約でゼロ除算は発生しないと保証されていますが、安全のためチェックを入れています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    n = int(data[0].strip())
    tokens = data[1].split()
    k = int(data[2].strip())
    flip_positions = set()
    if k > 0:
        flip_positions = set(map(int, data[3].split()))
    
    original_tokens = tokens.copy()
    flipped_tokens = tokens.copy()
    
    for pos in flip_positions:
        idx = pos - 1
        op = flipped_tokens[idx]
        if op == '+':
            flipped_tokens[idx] = '-'
        elif op == '-':
            flipped_tokens[idx] = '+'
        elif op == '*':
            flipped_tokens[idx] = '/'
        elif op == '/':
            flipped_tokens[idx] = '*'
    
    def evaluate(toks):
        stack = []
        for token in reversed(toks):
            if token in {'+', '-', '*', '/'}:
                a = stack.pop()
                b = stack.pop()
                if token == '+':
                    res = a + b
                elif token == '-':
                    res = a - b
                elif token == '*':
                    res = a * b
                elif token == '/':
                    if a == 0 or b == 0:
                        res = 0
                    else:
                        sign = 1
                        if (a < 0) != (b < 0):
                            sign = -1
                        res = sign * (abs(a) // abs(b))
                stack.append(res)
            else:
                stack.append(int(token))
        return stack[0]
    
    original_result = evaluate(original_tokens)
    flipped_result = evaluate(flipped_tokens)
    
    print(original_result)
    print(flipped_result)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。