概要

時間とともに川の流れが切り替わり、それに応じて高橋君の移動速度が変化します。各質問の時刻 \(X_j\) における高橋君の座標を求める問題です。

考察

まず、各時間帯における高橋君の「地面に対する速度」を整理しましょう。

• 時刻 \(0\) 以上 \(T_1\) 未満：流れがないので速度は \(0\)（その場に留まる）。
• 時刻 \(T_i\) 以上 \(T_{i+1}\) 未満（\(1 \leq i \leq N-1\)）：流れの速度が \(W_i\) なので、
  • \(W_i > 0\)（東向き）のとき、速度は \(W_i + V\)
  • \(W_i < 0\)（西向き）のとき、速度は \(W_i - V\)
• 時刻 \(T_N\) 以降：同様に \(W_N\) に応じた速度。

つまり各時間帯ごとに一定の速度で等速直線運動をするので、座標は時間に対して区分的に線形（折れ線）で変化します。

素朴なアプローチの問題点

質問のたびに時刻 \(0\) から \(X_j\) まで各区間の移動量を足し合わせていくと、1 回の質問に \(O(N)\) かかり、全体で \(O(NQ)\) となります。\(N, Q\) が最大 \(10^5\) 規模なので、これは間に合いません。

解決方法

座標が折れ線で変化することに注目します。各「折れ目」となる時刻 \(T_k\) における座標 \(\mathrm{pos}[k]\) をあらかじめ前計算しておけば、質問時刻 \(X_j\) が含まれる区間さえ分かれば、

\[ \text{答え} = \mathrm{pos}[k] + (\text{区間 } k \text{ の速度}) \times (X_j - T_k) \]

で一発で求められます。区間の特定は、\(T\) がソート済みであることを利用して二分探索で行えば \(O(\log N)\) で済みます。

アルゴリズム

1. 速度の前計算: 各 \(i\) について地面に対する速度 \(v_i\) を求める。
   • \(W_i > 0\) なら \(v_i = W_i + V\)、\(W_i < 0\) なら \(v_i = W_i - V\)。
2. 折れ目での座標の前計算: \(\mathrm{pos}[0] = 0\)（時刻 \(T_0 = T_1\) での座標は \(0\)、なぜなら時刻 \(T_1\) までは静止しているため）とし、 $\( \mathrm{pos}[k] = \mathrm{pos}[k-1] + v_{k-1} \cdot (T_k - T_{k-1}) \)\( を \)k = 1, 2, \ldots, N-1$ について累積的に計算する。
3. 各質問の処理:
   • \(X_j < T_1\) なら、まだ流れがないので答えは \(0\)。
   • そうでなければ二分探索で \(T_k \leq X_j\) を満たす最大の \(k\) を求め、 $\( \mathrm{pos}[k] + v_k \cdot (X_j - T_k) \)$ を出力する。

具体例で確認します。例えば時刻 \(T_1\) までは座標 \(0\)、その後 \(T_1\) から \(T_2\) の間は速度 \(v_1\) で動くので、時刻 \(X\)（\(T_1 \leq X < T_2\)）での座標は \(0 + v_1 \cdot (X - T_1)\) となります。これは上の式で \(k=1\)（\(\mathrm{pos}[1]\) は使わず \(\mathrm{pos}[0]=0\) を起点に計算）に対応します（コードでは区間の始点 \(T_k\) と座標 \(\mathrm{pos}[k]\) を対応させて扱っています）。

計算量

• 時間計算量: 前計算が \(O(N)\)、各質問が二分探索で \(O(\log N)\) なので、全体で \(O(N + Q \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 二分探索: Python では bisect_right(T, X) - 1 で「\(T_k \leq X\) を満たす最大の \(k\)」を得られます。これが質問時刻 \(X\) を含む区間のインデックスになります。

• 時刻 \(T_1\) 未満の扱い: 流れが始まる前（\(X < T_1\)）は座標 \(0\) なので、二分探索の前に個別に判定すると安全です。

• オーバーフロー: 速度と時間の積が大きくなるため、64bit 整数の範囲を意識する必要があります（問題で 64bit に収まることが保証されています）。Python では多倍長整数なので自動的に扱えます。

• 入出力の高速化: \(Q\) が大きいため、入力は一括読み込み、出力は文字列をまとめて一度に出力すると高速です。

  ソースコード

import sys
from bisect import bisect_right

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx+=1
    V = int(data[idx]); idx+=1
    Q = int(data[idx]); idx+=1
    T = [0]*N
    v = [0]*N
    for i in range(N):
        t = int(data[idx]); idx+=1
        w = int(data[idx]); idx+=1
        T[i] = t
        if w > 0:
            v[i] = w + V
        else:
            v[i] = w - V
    # pos[k] = position at time T[k]
    pos = [0]*N
    for k in range(1, N):
        pos[k] = pos[k-1] + v[k-1]*(T[k]-T[k-1])
    
    out = []
    t0 = T[0]
    for _ in range(Q):
        X = int(data[idx]); idx+=1
        if X < t0:
            out.append('0')
        else:
            j = bisect_right(T, X) - 1
            ans = pos[j] + v[j]*(X - T[j])
            out.append(str(ans))
    sys.stdout.write('\n'.join(out) + '\n')

main()

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