概要

長さ \(L\) の廊下を往復運動する \(N\) 台のロボットについて、時刻 \(T\) での座標を求める問題です。各ロボットは壁で反射しながら移動し、初期位置と速度が与えられます。

考察

各ロボットの運動は独立で、反射を考慮する必要があります。素朴に時間 \(T\) の間の移動をシミュレーションすると、\(T\) が最大 \(10^9\) と大きいため計算量が大きくなり、TLE（時間制限超過）になります。

重要な観察は、反射後の運動が周期的になることです。ロボットが壁で反射するたびに移動方向が反転しますが、\(2L\) の距離を移動するごとに元の状態に戻る（周期2の運動）と考えることができます。つまり、移動距離を \(2L\) で割った余りを考えることで、効率的に最終位置を計算できます。

アルゴリズム

各ロボットについて、以下の手順で最終位置を計算します：

1. 速度が0の場合: 移動しないので、初期位置 \(x\) をそのまま出力します。
2. 正の方向に移動する場合（\(v > 0\)）:
   • 総移動距離を \(d = T \times v\) とします。
   • 初期位置が0の場合:
     • \(d\) を \(L\) で割った商（周期数）と余りを計算します。
     • 周期数が偶数の場合: 余りがそのまま座標になります。
     • 周期数が奇数の場合: \(L\) から余りを引いた値が座標になります。
   • 初期位置が0以外の場合:
     • まず右端までの距離 \(L - x\) を移動します。
     • 残りの移動距離で周期運動を計算します（上記と同様）。
3. 負の方向に移動する場合（\(v < 0\)）:
   • 総移動距離を \(d = T \times |v|\) とします。
   • 初期位置が \(L\) の場合:
     • \(d\) を \(L\) で割った商と余りを計算します。
     • 周期数が偶数の場合: \(L\) から余りを引いた値が座標になります。
     • 周期数が奇数の場合: 余りがそのまま座標になります。
   • 初期位置が \(L\) 以外の場合:
     • まず左端までの距離 \(x\) を移動します。
     • 残りの移動距離で周期運動を計算します。

このように、移動距離を廊下の長さ \(L\) で割った余りを利用することで、反射を効率的に扱います。

計算量

• 時間計算量: \(O(N)\)
  • 各ロボットに対して定数時間で計算できるため。
• 空間計算量: \(O(N)\)
  • 入力と結果を格納するための空間。

実装のポイント

• 初期位置が壁上（0または\(L\)）の場合とそれ以外の場合で処理を分けます。

• 周期運動の計算では、移動距離を廊下の長さで割った商の偶奇で反射後の方向を判定します。

• 整数演算のみを使用するため、浮動小数点誤差の心配がありません（問題で整数保証されている）。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    L = int(data[1])
    T = int(data[2])
    index = 3
    robots = []
    for i in range(n):
        x = int(data[index])
        v = int(data[index+1])
        index += 2
        robots.append((x, v))
    
    results = []
    for x, v in robots:
        if v == 0:
            results.append(x)
            continue
            
        if v > 0:
            total_dist = T * v
            if x == 0:
                cycle = total_dist // L
                rem = total_dist % L
                if cycle % 2 == 0:
                    pos = rem
                else:
                    pos = L - rem
            else:
                dist_to_right = L - x
                if total_dist <= dist_to_right:
                    pos = x + total_dist
                else:
                    total_dist -= dist_to_right
                    cycle = total_dist // L
                    rem = total_dist % L
                    if cycle % 2 == 0:
                        pos = L - rem
                    else:
                        pos = rem
        else:
            v_abs = -v
            total_dist = T * v_abs
            if x == L:
                cycle = total_dist // L
                rem = total_dist % L
                if cycle % 2 == 0:
                    pos = L - rem
                else:
                    pos = rem
            else:
                dist_to_left = x
                if total_dist <= dist_to_left:
                    pos = x - total_dist
                else:
                    total_dist -= dist_to_left
                    cycle = total_dist // L
                    rem = total_dist % L
                    if cycle % 2 == 0:
                        pos = rem
                    else:
                        pos = L - rem
        
        results.append(pos)
    
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。