概要

長さ \(L\) の廊下の中で、各ロボットが与えられた初期位置と速度で動き、両端で跳ね返るとき、時刻 \(T\) における各ロボットの位置を求める問題。

考察

この問題では、ロボットが両端で跳ね返るという条件があるため、素直にシミュレーションすると非常に時間がかかります。特に、\(T\) が最大 \(10^9\) まであり得るので、1秒ずつ時間を進めて位置を更新するような方法では到底間に合いません（TLE）。

重要な考察は、「ロボットが廊下内で往復する動きは、ある周期的なパターンを持つ」ということです。廊下の長さが \(L\) であれば、ロボットが一往復するのに必要な距離は \(2L\) です。つまり、ロボットの動きは周期 \(2L\) で繰り返されます。

したがって、ロボットがある方向に一直線に進んだと仮定してその座標を求め、それを周期的に折り返して実際の位置を求めるという方法が有効です。これにより、時間計算量を大幅に削減できます。

また、初期状態でロボットが端（座標 \(0\) または \(L\)）にいて、その向きが壁に向かっている場合、時刻 \(0\) で反射が起こることに注意が必要です。この処理を忘れると、WAになります。

アルゴリズム

各ロボットについて以下の手順で時刻 \(T\) の位置を計算します：

1. 速度が \(0\) の場合は、初期位置のままなのでそのまま出力。
2. 初期位置が端にある場合：
   • 座標 \(0\) で \(V_i < 0\) なら、速度を反転させる。
   • 座標 \(L\) で \(V_i > 0\) なら、速度を反転させる。
3. 時刻 \(T\) における移動距離を dist = |V_i| * T として計算。
4. ロボットが進む方向に応じて仮の最終座標 pos を計算：
   • 正方向なら x + dist
   • 負方向なら x - dist
5. この pos を周期 \(2L\) で折り返して、廊下内の実際の座標に変換：
   • pos を 2L で剰余を取る（ただし負の数にも対応）。
   • 得られた値が \([0, L]\) を超えていたら、再度折り返す（\(2L - pos\)）。

これにより、高速かつ正確に最終位置を求めることができます。

例

例えば、\(L = 5\), \(T = 7\), 初期位置 \(x = 1\), 速度 \(v = 2\) の場合： - 移動距離: \(2 \times 7 = 14\) - 仮の位置: \(1 + 14 = 15\) - 周期 \(2L = 10\) で剰余: \(15 \bmod 10 = 5\) - まだ範囲外（\(5 = L\) なのでOK）→ 最終位置は \(5\)

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

各ロボットに対して定数時間の計算を行うので、全体で線形時間で解けます。

実装のポイント

• 初期状態での反射処理（時刻0での速度反転）を忘れずに実装すること。

• 剰余演算 % は負の数に対しても正しく動作するように注意（Pythonの % は安全）。

• 廊下の長さが \(0\) の場合（\(L = 0\)）は、すべてのロボットが常に座標 \(0\) にいることに注意。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    robots = []
    for _ in range(N):
        x = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        robots.append((x, v))
    
    result = []
    for x, v in robots:
        if v == 0:
            result.append(x)
            continue
        
        # 初期位置での反射処理
        if x == 0 and v < 0:
            v = -v
        elif x == L and v > 0:
            v = -v
        
        # 移動距離
        dist = abs(v) * T
        if v > 0:
            pos = x + dist
        else:
            pos = x - dist
        
        # 廊下の範囲 [0, L] で折り返す周期的性質を利用する
        # パターンの周期は 2*L
        period = 2 * L
        if period == 0:
            # L=0の場合、全ロボットは常に0にいる
            result.append(0)
            continue
            
        # pos を period で剰余を取る（ただし負の数にも対応）
        pos = pos % period
        
        # [0, L] の範囲内に収める
        if pos <= L:
            final_pos = pos
        else:
            final_pos = 2 * L - pos
            
        result.append(final_pos)
    
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。