概要

直線上に並んだ地点 \(1\) から \(N\) のうち、高橋君が移動する区間 \([S, T]\)（または \([T, S]\)）に含まれる桜の木を探し、それらの花びらの総数を求める問題です。

考察

この問題を解くための重要なポイントは、「高橋君がどの地点を通過するか」を正確に把握することです。

高橋君は地点 \(S\) から \(T\) まで最短距離で移動します。 - \(S \leq T\) の場合：地点 \(S, S+1, \ldots, T\) を通過します。 - \(S > T\) の場合：地点 \(S, S-1, \ldots, T\) を通過します。

どちらの場合も、通過する地点は「\(\min(S, T)\) 以上 \(\max(S, T)\) 以下」の範囲にあるすべての整数地点です。

注意点

地点の数 \(N\) は最大で \(10^9\) と非常に大きいため、「地点 \(1\) から順に調べていく」ような \(O(N)\) の解法では実行時間制限に間に合いません。 一方で、桜の木の数 \(M\) は \(2 \times 10^5\) 程度であるため、「すべての桜の木を 1 つずつ確認する」という \(O(M)\) のアプローチであれば十分に間に合います。

アルゴリズム

1. 高橋君が訪れる範囲の下限を \(low = \min(S, T)\)、上限を \(high = \max(S, T)\) とします。
2. 合計の花びら枚数を保持する変数 total_petals を \(0\) で初期化します。
3. \(M\) 本の桜の木それぞれについて、以下の処理を行います。
   • \(i\) 番目の桜の木の地点 \(P_i\) が、\(low \leq P_i \leq high\) を満たすか判定する。
   • 満たす場合、total_petals に \(V_i\) を加算する。
4. 最終的な total_petals を出力します。

計算量

• 時間計算量: \(O(M)\)
  • 桜の木の数 \(M\) に対して 1 回ずつループを回すため、地点数 \(N\) に依存せず高速に処理できます。
• 空間計算量: \(O(M)\)
  • 入力された桜の木の情報をリスト等で保持する場合に必要となります。

実装のポイント

• 大きな数の扱い: 花びらの総数は最大で \(M \times \max(V_i) \approx 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達します。Pythonの整数型（int）は自動的に多倍長整数として扱われるため、オーバーフローを気にせず計算できます。

• 高速な入出力: \(M\) が大きいため、input() を繰り返すよりも sys.stdin.read().split() などを用いて一括で入力を読み込む方が実行時間を短縮できます。

• 範囲の判定: \(S < T\) と \(S > T\) の両方に対応できるよう、min と max を使って移動範囲の境界を定めておくと実装がシンプルになります。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにします。
    # これは大量の入力を高速に処理するための定石です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 地点の数 (この問題の解法には直接使用しません)
    # M: 桜の木の数
    # S: スタート地点
    # T: ゴール地点
    m = int(input_data[1])
    s = int(input_data[2])
    t = int(input_data[3])
    
    # 高橋君が移動する範囲を [low, high] として定めます。
    # 最短距離で移動するため、訪れる地点は min(S, T) から max(S, T) の間の全整数です。
    if s <= t:
        low, high = s, t
    else:
        low, high = t, s
        
    total_petals = 0
    
    # 桜の木の情報は input_data のインデックス 4 以降に P_i, V_i の順で並んでいます。
    # map(int, ...) を使って文字列を整数に変換するイテレータを作成します。
    it = map(int, input_data[4:])
    
    # イテレータから要素を2つずつ取り出して処理します（P_i: 地点, V_i: 花びらの枚数）。
    for p in it:
        try:
            v = next(it)
            # 桜の木の地点 p が移動範囲 [low, high] に含まれているか判定します。
            if low <= p <= high:
                total_petals += v
        except StopIteration:
            # 予期せぬ入力終了に対する安全策です。
            break
            
    # 合計の花びら枚数を出力します。
    # Pythonの整数型は非常に大きな値も扱えるため、オーバーフローの心配はありません。
    print(total_petals)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。