概要

壁で反射しながら廊下を往復するロボットの、時刻 \(T\) における座標を求める問題です。反射の挙動を「折り返し（フォールディング）」の考え方で数学的に処理することで、各ロボットについて \(O(1)\) で答えを求められます。

考察

壁がなかった場合を考える

もし壁がなければ、ロボット \(i\) の時刻 \(T\) での座標は単に \(X_i + V_i \times T\) です。しかし実際には区間 \([0, L]\) の両端で反射するため、この値が範囲外になることがあります。

反射をシミュレーションするのは非効率

\(T\) が最大 \(10^9\)、\(|V_i|\) も最大 \(10^9\) なので、反射回数は膨大になり得ます。1回ずつ反射をシミュレーションするのは到底間に合いません。

折り返し（フォールディング）のテクニック

ここで重要な観察は、区間 \([0, L]\) での反射運動は、周期 \(2L\) の折り返しパターンとして捉えられるということです。

壁がないと仮定した座標 \(p = X_i + V_i \times T\) を考えます。ロボットは \(0 \to L \to 0 \to L \to \cdots\) と往復しており、これは数直線上の座標を \(2L\) 周期で「ジグザグに折り畳む」操作に対応します。

具体的には：

1. \(p\) を \(2L\) で割った余り \(r\)（\(0 \leq r < 2L\)）を求める
2. \(r \leq L\) なら、答えは \(r\)
3. \(r > L\) なら、答えは \(2L - r\)（折り返し）

具体例（\(L = 5\) の場合）： - \(p = 7\) → \(r = 7 \bmod 10 = 7\) → \(7 > 5\) なので \(10 - 7 = 3\) - これは、座標 \(0\) から出発して \(5\) まで行き（+5）、反射して \(2\) 戻る（-2）ので座標 \(3\) に対応します。

時刻 \(0\) での壁上の反射処理

問題文にある通り、初期位置が壁上で壁に向かう速度を持つ場合は時刻 \(0\) で即座に反転します。これはコード中で \(V\) の符号を反転させることで対応します。

アルゴリズム

各ロボット \(i\) について以下を行います：

1. 初期反転の処理: \(X_i = 0\) かつ \(V_i < 0\) なら \(V_i \leftarrow -V_i\)、\(X_i = L\) かつ \(V_i > 0\) なら \(V_i \leftarrow -V_i\)
2. 壁なし座標の計算: \(p = X_i + V_i \times T\)
3. 折り返しによる座標の決定:
   • \(r = p \bmod 2L\)（Python の % 演算子は負の数に対しても非負の余りを返す）
   • \(r \leq L\) なら答えは \(r\)、そうでなければ答えは \(2L - r\)

計算量

• 時間計算量: \(O(N)\)（各ロボットについて \(O(1)\) の計算）
• 空間計算量: \(O(N)\)（出力の格納）

実装のポイント

• Python の % 演算子の挙動: Python では負の数に対しても a % m（\(m > 0\)）は \([0, m)\) の範囲の値を返します。これにより、\(p\) が負になる場合でも追加の場合分けなく正しく処理できます。

• \(L = 0\) の特殊ケース: \(L = 0\) のとき全ロボットは座標 \(0\) にしかいられないので、\(2L\) での除算を避けるために別途処理しています。

• 整数演算のみ: 問題の保証により答えは整数なので、浮動小数点演算を使わず整数のみで正確に計算できます。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    L = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    out = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        
        # Handle initial reflection at walls at time 0
        if X == 0 and V < 0:
            V = -V
        elif X == L and V > 0:
            V = -V
        
        # Position without walls
        pos = X + V * T
        
        # Reflect into [0, L] using the folding method
        # The robot bounces in a "zigzag" pattern with period 2L
        # Map pos into [0, 2L) cycle, then fold
        if L == 0:
            out.append(0)
            continue
        
        # We need to fold pos into [0, L]
        # First, normalize pos modulo 2L into [0, 2L)
        cycle = 2 * L
        pos_mod = pos % cycle  # Python's modulo ensures non-negative result for positive cycle
        
        if pos_mod <= L:
            result = pos_mod
        else:
            result = cycle - pos_mod
        
        out.append(result)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

---

この解説は claude4.6opus-thinking によって生成されました。