概要

地点 \(S\) から地点 \(T\) まで最短距離で移動するとき、通過する区間内にある桜の木から落ちる花びらの総数を求める問題です。

考察

重要な気づき

1. 最短距離で移動するということは、\(S\) から \(T\) に向かって一直線に進むことを意味します。つまり、\(S\) と \(T\) の間にある地点のみを通過します。

2. 例えば \(S = 2\), \(T = 5\) の場合、通過する地点は \(2, 3, 4, 5\) です。\(S = 5\), \(T = 2\) の場合も、通過する地点は同じく \(2, 3, 4, 5\) です（進む方向が逆なだけ）。

3. つまり、\(\min(S, T)\) から \(\max(S, T)\) までの区間にある桜の木からの花びらを集計すればよいのです。

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

素朴に「地点 \(1\) から \(N\) まですべてチェックする」方法では、\(N\) が最大 \(10^9\) もあるため、\(O(N)\) の計算量となりTLE（時間超過）になります。

解決策

\(N\) は大きいですが、桜の木の本数 \(M\) は最大 \(2 \times 10^5\) と小さいです。すべての地点をチェックするのではなく、桜の木がある地点のみをチェックすればよいのです。

アルゴリズム

1. スタート地点 \(S\) とゴール地点 \(T\) から、移動区間 \([\text{left}, \text{right}]\) を決定する

   • \(\text{left} = \min(S, T)\)
   • \(\text{right} = \max(S, T)\)

2. 各桜の木について、その位置 \(P_i\) が移動区間内にあるかをチェックする

   • \(\text{left} \leq P_i \leq \text{right}\) なら、花びらの枚数 \(V_i\) を合計に加算

3. 合計を出力する

具体例

N=10, M=3, S=3, T=7
桜の木: (P=2, V=100), (P=5, V=200), (P=8, V=300)

移動区間は \([3, 7]\) です。 - \(P=2\): 区間外（\(2 < 3\)）→ カウントしない - \(P=5\): 区間内（\(3 \leq 5 \leq 7\)）→ \(200\) を加算 - \(P=8\): 区間外（\(8 > 7\)）→ カウントしない

答え: \(200\)

計算量

• 時間計算量: \(O(M)\)
  • \(M\) 本の桜の木それぞれについて、区間内かどうかを \(O(1)\) で判定
• 空間計算量: \(O(1)\)
  • 桜の木の情報を保存せず、読み込みながら処理するため定数空間

実装のポイント

1. 区間の端点の決定: \(S\) と \(T\) の大小関係は問題文で指定されていないため、min と max を使って区間を正規化する必要があります。

2. オーバーフロー対策: \(V_i\) が最大 \(10^9\)、\(M\) が最大 \(2 \times 10^5\) なので、合計は最大約 \(2 \times 10^{14}\) になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

3. 入力の効率的な処理: 桜の木の情報をすべて配列に格納してからソートするなどの処理は不要です。読み込みながら判定・加算することで、空間効率を良くできます。

   ソースコード

def main():
    N, M = map(int, input().split())
    S, T = map(int, input().split())
    
    # 移動区間を決定
    left = min(S, T)
    right = max(S, T)
    
    total = 0
    for _ in range(M):
        P, V = map(int, input().split())
        # 桜の木が移動区間内にあるかチェック
        if left <= P <= right:
            total += V
    
    print(total)

if __name__ == "__main__":
    main()

---

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