概要

各来場者のチケット種類に応じて払い戻し額（全額または半額切り捨て）を計算し、その合計を求める問題です。

考察

払い戻し額は来場者ごとに独立に決まります。

• normal なら購入金額 \(P_i\) をそのまま加算
• half なら \(\left\lfloor \dfrac{P_i}{2} \right\rfloor\)（整数除算）を加算

したがって、全員分を順に読み取りながら合計に足していけば十分です。

具体例： - normal 100 → \(100\) - half 101 → \(101/2=50.5\) なので端数切り捨てで \(50\) 合計は \(150\) になります。

制約は \(N \le 2 \times 10^5\) と大きいため、入力を 1 行ずつ input() で読む実装でも間に合うことは多いですが、Pythonでは環境によっては遅くなる可能性があります。そこで、提出コードでは sys.stdin.buffer.read() を使って高速にまとめ読みし、TLEリスクを下げています。

アルゴリズム

1. 入力から \(N\) を読む
2. \(N\) 人について以下を繰り返す
   
   • チケット種類 \(T_i\) と金額 \(P_i\) を読む
   • \(T_i=\texttt{normal}\) なら total += P_i
   • \(T_i=\texttt{half}\) なら total += P_i // 2
3. total を出力する

ポイントは「半額（端数切り捨て）」が Python の整数除算 // に対応することです。

計算量

• 時間計算量: \(O(N)\)（各来場者を 1 回ずつ処理）
• 空間計算量: \(O(1)\)（合計値など定数個の変数のみ）
  • ただし実装では入力をまとめ読みしているため、実際の使用メモリは入力サイズに比例します。

実装のポイント

• 半額の「端数切り捨て」は p // 2 を使う（p / 2 だと浮動小数になり不適切）

• 高速入力のために sys.stdin.buffer.read().split() を使うと、\(N\) が大きい場合でも安定して高速に処理できる

• read().split() は bytes を返すので、チケット種類の比較のために decode() して文字列にしている

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    total = 0
    idx = 1
    for _ in range(n):
        t = data[idx].decode()
        p = int(data[idx + 1])
        if t == "normal":
            total += p
        else:  # "half"
            total += p // 2
        idx += 2
    print(total)

if __name__ == "__main__":
    main()

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