概要

\(N\) 人の来場者に対し、チケットの種類（normal または half）に応じて払い戻し金額を計算し、その合計を求める問題です。

考察

各来場者について、問題文で指定された以下のルールに従って払い戻し額を計算する必要があります。 - チケットが normal の場合：購入金額 \(P_i\) をそのまま払い戻す。 - チケットが half の場合：購入金額の半分 \(\lfloor P_i / 2 \rfloor\)（端数切り捨て）を払い戻す。

この問題を解く上でのポイントは以下の通りです。 1. 条件分岐: チケットの種類を文字列として受け取り、if 文を用いて種類に応じた計算を行います。 2. 端数切り捨ての処理: 「半分（端数切り捨て）」の計算は、プログラミング言語における「整数同士の割り算（整数除算）」を用いることで、特別な処理を書かずに実現できます。 3. 合計値の大きさ: \(N\) が最大 \(2 \times 10^5\)、各 \(P_i\) が最大 \(10^5\) であるため、合計金額は最大で \(2 \times 10^{10}\) 程度になります。Python は標準で非常に大きな整数（多倍長整数）を扱えるため、一般的な 32bit 整数型の範囲（約 \(2 \times 10^9\)）を超える場合でも、オーバーフローを気にせず計算が可能です。

アルゴリズム

1. 合計払い戻し額を保持する変数 total_refund を \(0\) で初期化します。
2. 来場者の人数 \(N\) を読み込みます。
3. 各来場者 \(i = 1, 2, \dots, N\) について、以下の処理を繰り返します。
   • チケットの種類 \(T_i\) と金額 \(P_i\) を取得する。
   • \(T_i\) が normal ならば、total_refund に \(P_i\) を加算する。
   • \(T_i\) が half ならば、total_refund に \(P_i // 2\)（整数除算）を加算する。
4. 最終的な total_refund の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 人のデータを 1 回ずつ順番に処理するため、人数に比例した時間で計算が完了します。
• 空間計算量: \(O(N)\)
  • 今回の実装では sys.stdin.read().split() を用いて入力データ全体を一度にメモリ上に読み込んでいるため、入力のサイズに比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) の値が大きいため、input() 関数を \(N\) 回呼び出すよりも、sys.stdin.read().split() を使って全ての入力を一括で取得し、リストとして処理する方が実行時間を大幅に短縮できます。

• 整数除算の演算子: Python では / を使うと結果が浮動小数点数（float型）になりますが、// を使うことで端数を切り捨てた整数（int型）を直接得ることができます。これにより、浮動小数点数の精度問題を回避できます。

  ソースコード

import sys

def main():
    # 入力を一括で読み込み、空白文字で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初の要素は人数 N
    n = int(input_data[0])
    total_refund = 0
    
    # 各来場者のデータを処理
    for i in range(n):
        # チケットの種類 T_i と購入金額 P_i を取得
        t = input_data[1 + 2 * i]
        p = int(input_data[2 + 2 * i])
        
        if t == 'normal':
            # 一般チケットは全額払い戻し
            total_refund += p
        elif t == 'half':
            # 学割チケットは半額（端数切り捨て）を払い戻し
            total_refund += p // 2
            
    # 合計金額を出力
    print(total_refund)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。