概要

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

考察

重要な気づき

ポーランド記法の式は「演算子が先、オペランドが後」に並ぶため、トークン列を右から左へ見ると処理が簡単になります。

• 右から見ていくと、まず数（部分式の値）が現れてスタックに積まれる
• 演算子が現れたとき、スタックの先頭2つがその演算子のオペランドになっている
  （op A B の形なので、右から読むと先に \(A,B\) の値が揃う）

例えば * + 3 5 2 を右から読むと

• 2 を積む
• 5 を積む
• 3 を積む
• + が来たので \(3+5=8\) にして積む
• * が来たので \(8*2=16\) にして積む

最後にスタックに残る1つが答えです。

素朴な方法が危ない理由

再帰的定義通りに「式を再帰でパースして評価」すると、最悪で再帰の深さが \(O(N)\) になり、\(N \le 2\times 10^5\) では 再帰上限やスタックオーバーフローの危険があります。また、式木を構築するのもメモリ・実装が重くなりがちです。

そこで、反復（ループ）＋スタックで一度なめるだけで評価します。

反転後の式の扱い

反転される位置 \(p_i\) は入力で与えられるので、

• 長さ \(N\) の boolean 配列 flip を用意し、flip[p_i]=True にする
• 評価時に、その位置のトークンが演算子なら反転してから計算する

とすれば、反転後も同じ評価ロジックで処理できます。

アルゴリズム

1. 入力のトークン列 t_1..t_N を配列で持つ。
2. 反転位置集合 \(\{p_i\}\) から、配列 flip（長さ \(N\)）を作る（\(1\)-indexed を \(0\)-indexed に直す）。
3. 関数 evaluate(tokens, flip) で評価する：
   • スタック st を空で用意
   • \(i=N-1\) から \(0\) まで逆順に見る
     • tokens[i] が演算子（+,-,*,/ の1文字）なら

          - 必要なら `flip[i]` に応じて演算子を反転
          - `a=st.pop()`, `b=st.pop()` を取り出し、`a op b` を計算して push
       

     • そうでなければ整数なので int(tokens[i]) を push
   • 最後に st[0] が式全体の値
4. flip=None で元の式、flip を渡して反転後の式をそれぞれ評価して出力する。

0方向への切り捨て除算（truncated division）

Pythonの // は負数で「負の無限大方向」へ丸めるため、問題の定義（\(0\) 方向へ切り捨て）と一致しません。
そこで - 商の絶対値を abs(a)//abs(b) で求め、 - 符号だけを (a<0) xor (b<0) で付け直す

ことで、定義通りの \(a/b\)（truncated）を実装しています。

計算量

• 時間計算量: \(O(N)\)（1回の評価が \(O(N)\)、これを2回行うので全体でも \(O(N)\)）
• 空間計算量: \(O(N)\)（スタックと flip 配列。flip が不要なときは作らない）

実装のポイント

• トークンが演算子かどうかは「1文字で +,-,*,/ に完全一致するか」で判定する必要があります。-3 は演算子ではなく整数です。

• 右から左への走査では、演算子のときに取り出す順番が重要で、a=pop(), b=pop() として a op b を計算します（op A B の順を保つため）。

• 除算は必ず tdiv(a,b) を使い、Pythonの // をそのまま使わないようにします。

  ソースコード

import sys

def tdiv(a: int, b: int) -> int:
    q = abs(a) // abs(b)
    return -q if (a < 0) ^ (b < 0) else q

def evaluate(tokens, flip):
    st = []
    for i in range(len(tokens) - 1, -1, -1):
        tok = tokens[i]
        if tok == b'+' or tok == b'-' or tok == b'*' or tok == b'/':
            op = tok
            if flip is not None and flip[i]:
                if op == b'+':
                    op = b'-'
                elif op == b'-':
                    op = b'+'
                elif op == b'*':
                    op = b'/'
                else:
                    op = b'*'
            a = st.pop()
            b = st.pop()
            if op == b'+':
                st.append(a + b)
            elif op == b'-':
                st.append(a - b)
            elif op == b'*':
                st.append(a * b)
            else:
                st.append(tdiv(a, b))
        else:
            st.append(int(tok))
    return st[0]

def main():
    data = sys.stdin.buffer.read().split()
    it = 0
    N = int(data[it]); it += 1
    tokens = data[it:it+N]; it += N
    K = int(data[it]); it += 1

    flip = None
    if K > 0:
        flip = [False] * N
        for j in range(K):
            p = int(data[it + j]) - 1
            flip[p] = True
        it += K

    ans1 = evaluate(tokens, None)
    ans2 = evaluate(tokens, flip)
    sys.stdout.write(f"{ans1}\n{ans2}\n")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。