概要

この問題は、長さ \(M\) の区間内を移動するボールが端点で反射を繰り返す様子をシミュレートする問題です。ショットの回数 \(N\) と移動距離 \(A_i\) が非常に大きいため、1 回ずつの反射を愚直に追うのではなく、数学的な性質（鏡像法や周期性）を利用して各ショットの結果を \(O(1)\) で計算する必要があります。

考察

1. 反射の性質と鏡像法

ボールが \([0, M]\) の範囲で反射を繰り返す様子は、数直線を \(M\) ごとに折り返したモデルで考えると分かりやすくなります。

• 座標 \(x\) が \(0 \le x \le M\) のとき：そのままの位置 \(x\)
• 座標 \(x\) が \(M < x \le 2M\) のとき：折り返されて \(2M - x\)
• 座標 \(x\) が \(2M < x \le 3M\) のとき：さらに折り返されて \(x - 2M\)

このように、ボールの動きは周期 \(2M\) の動きとして捉えることができます。ある位置 \(P\) から距離 \(A\) だけ右に移動する場合、最終的な位置は \((P + A) \pmod{2M}\) の値によって決まります。

2. 反射回数の計算

ボールが端点 \(0\) または \(M\) に到達するたびに反射が発生します。 現在地 \(P\) から右向きに距離 \(A\) だけ移動する場合を考えます（ただし \(0 \le P < M\) とします）。 このとき、最初の反射は \(M\) 地点で起こり、その後は \(M\) 距離進むごとに反射が起こります。 したがって、反射回数は \(\lfloor (P + A - 1) / M \rfloor\) 回となります。 ※ \(P+A\) がちょうど \(M\) の倍数のとき、その地点での反射を含めるために \(-1\) して調整しています。

3. 特殊な反射（開始時の反射）

問題文には「開始時点で端点にあり、外側に向かおうとする場合は即座に反射する」というルールがあります。 - 位置 \(0\) で L 方向：即座に反射して R 方向へ移動開始（反射 +1） - 位置 \(M\) で R 方向：即座に反射して L 方向へ移動開始（反射 +1） この処理を各ショットの最初に行うことで、その後の移動を「内側に向かう移動」として統一して扱うことができます。

アルゴリズム

各ショットについて以下の手順で処理を行います。

1. 移動距離の確認: \(A_i = 0\) の場合は何もしません。
2. 初期反射の判定:
   • \(C_i = \text{'R'}\) かつ 現在地 \(P = M\) ならば、反射回数を +1 し、方向を「左」に設定。
   • \(C_i = \text{'L'}\) かつ 現在地 \(P = 0\) ならば、反射回数を +1 し、方向を「右」に設定。
   • それ以外は、指定された方向 \(C_i\) のまま移動を開始。
3. 移動後の位置と反射の計算:
   • 「左」向きに移動する場合は、座標系を反転させて（\(P' = M - P\)）「右」向きの移動として計算すると楽です。
   • 移動後の仮想座標を \(X = P + A\) とします。
   • 追加の反射回数 \(\lfloor (X - 1) / M \rfloor\) を加算します。
   • 最終的な位置 \(P\) を \(X \pmod{2M}\) を利用して求めます。
     • \(X \pmod{2M} \le M\) ならば \(P = X \pmod{2M}\)
     • \(X \pmod{2M} > M\) ならば \(P = 2M - (X \pmod{2M})\)
4. 座標系の復元: 手順 3 で反転させていた場合は、結果を元の座標系に戻します。

計算量

• 時間計算量: \(O(N)\) 各ショットを定数時間 \(O(1)\) で計算するため、ショット数 \(N\) に対して線形時間で終了します。
• 空間計算量: \(O(N)\) 入力を保持するために \(O(N)\) のメモリを使用します（ストリーム処理を行えば \(O(1)\) にすることも可能です）。

実装のポイント

• 大きな値の扱い: \(M\) や \(A_i\) が \(10^9\) と大きいため、計算過程で \(2M\) などの値が \(2 \times 10^9\) になります。Python では自動で多倍長整数として扱われますが、他の言語（C++など）では long long 型を使用する必要があります。

• 方向の統一: 左向きの移動を \(P' = M - P\) という変換で右向きに置き換える手法（鏡像の利用）は、条件分岐を減らしバグを防ぐのに非常に有効です。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と多いため、Python の場合は sys.stdin.read().split() などを用いて一括で読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # Fast input reading: read all at once and use an iterator
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    S = int(next(it))
    
    current_P = S
    total_reflections = 0
    
    # Process each of the N shots
    for _ in range(N):
        C = next(it)
        A = int(next(it))
        
        # If distance A is 0, no movement or reflection occurs
        if A == 0:
            continue
        
        # 1. Handle the "start-of-shot" reflection and determine initial direction
        # If at boundary 0 moving Left or boundary M moving Right, reflect immediately
        if C == 'R':
            if current_P == M:
                total_reflections += 1
                direction = -1
            else:
                direction = 1
        else: # C == 'L'
            if current_P == 0:
                total_reflections += 1
                direction = 1
            else:
                direction = -1
        
        # 2. Calculate the number of reflections and the final position for this shot
        # A reflection occurs every time the ball reaches 0 or M with distance remaining.
        # We use mirroring to unify the logic for both directions.
        if direction == 1:
            # Moving towards M from current_P
            # Let X be the distance from 0 in an infinite line model
            X = current_P + A
            # Reflections occur when crossing multiples of M (M, 2M, 3M, ...)
            # Since current_P < M, the first boundary hit is M.
            total_reflections += (X - 1) // M
            
            # Final position calculation within [0, 2M) period
            X_mod = X % (2 * M)
            if X_mod <= M:
                current_P = X_mod
            else:
                current_P = 2 * M - X_mod
        else: # direction == -1
            # Moving towards 0 from current_P
            # Mirror the coordinate system: P' = M - P
            # Moving from P towards 0 is equivalent to moving from P' towards M
            P_prime = M - current_P
            X = P_prime + A
            total_reflections += (X - 1) // M
            
            # Final position calculation on the mirrored table
            X_mod = X % (2 * M)
            if X_mod <= M:
                P_prime_final = X_mod
            else:
                P_prime_final = 2 * M - X_mod
            # Transform back from mirrored coordinate
            current_P = M - P_prime_final
            
    # Output the final position and total reflection count
    sys.stdout.write(f"{current_P} {total_reflections}\n")

if __name__ == '__main__':
    solve()

---

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