概要

この問題は、電気自動車で \(N\) 個の区間を完走できるかを判定するシミュレーション問題です。各区間でのバッテリー消費と、特定の場所にある充電ステーションでの回復を順番に計算していきます。

考察

重要なルール

1. 走行の条件: 区間 \(i\) を走行する直前にバッテリー残量が \(1\) 以上であれば、その区間を走りきることができます。
2. 消費: 区間 \(i\) を走ると、バッテリーが \(D_i\) 減少します。
3. 充電（交換）: 充電ステーション \(j\) は区間 \(P_j\) と \(P_j + 1\) の間にあります。つまり、区間 \(P_j\) を走り終えた直後に利用できます。交換すると残量を \(S_j\) に書き換えることができます。

貪欲法（Greedy）の適用

充電ステーションでバッテリーを交換するかどうかの選択肢がありますが、この問題では「完走できるか」のみを問われています。 バッテリー残量は多ければ多いほど完走しやすくなるため、「現在のバッテリー残量よりも交換後の値 \(S_j\) の方が大きいなら、必ず交換する」という貪欲な戦略が最適です。

失敗する条件

シミュレーションの途中で、ある区間を走行しようとした時にバッテリー残量が \(0\) 以下（\(1\) 未満）であれば、その時点で到達不可能（No）と判定できます。

アルゴリズム

1. 現在のバッテリー残量を \(curr\_b = K\) とします。
2. 区間 \(i = 1, 2, \dots, N\) について、以下の処理を繰り返します：
   • もし \(curr\_b < 1\) なら、区間 \(i\) を走れないため No を出力して終了。
   • 区間 \(i\) を走行し、バッテリーを減らす： \(curr\_b = curr\_b - D_i\)。
   • もし区間 \(i\) の直後に充電ステーションがある場合（\(i = P_j\)）：
     • 現在の残量 \(curr\_b\) と \(S_j\) を比較し、 \(S_j > curr\_b\) なら \(curr\_b = S_j\) とする。
3. すべての区間を走り終えたら Yes を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 全ての区間を 1 回ずつ走査し、各充電ステーションの情報も 1 回ずつ確認するため、入力サイズに比例した時間で処理が終わります。
• 空間計算量: \(O(N + M)\)
  • 区間の消費量 \(D_i\) と充電ステーションの情報をリストに保持するために必要なメモリ量です。

実装のポイント

• 入力の高速化: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• ステーションの管理: 充電ステーションは \(P_j\) の昇順で与えられるため、キューやポインタを使って、現在の区間の直後にステーションがあるかどうかを効率的に判定できます。

• バッテリー残量の負の値: 区間走行後に \(curr\_b\) が \(0\) 以下になっても、その直後に充電ステーションがあり、そこで \(1\) 以上に回復すれば、次の区間を走行することが可能です。判定のタイミング（走行の「直前」）に注意しましょう。

  ソースコード

import sys

def solve():
    # Read all input tokens from standard input for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Use an iterator to process the tokens sequentially
    it = iter(input_data)
    
    # Read N (number of sections), M (number of charging stations), and K (initial battery)
    try:
        N = int(next(it))
        M = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # Read D_i: the battery consumption for each section i
    # D is stored in a list where D[0] corresponds to section 1, D[1] to section 2, etc.
    try:
        D = [int(next(it)) for _ in range(N)]
    except StopIteration:
        return
    
    # curr_b represents the current battery level of the electric vehicle
    curr_b = K
    
    # Stations are located between sections P_j and P_j + 1.
    # We store the next station's position (next_p) and its exchange value (next_s).
    if M > 0:
        try:
            next_p = int(next(it))
            next_s = int(next(it))
            stations_left = M - 1
        except StopIteration:
            next_p = None
            next_s = None
            stations_left = 0
    else:
        next_p = None
        next_s = None
        stations_left = 0
        
    # Iterate through all sections from 1 to N
    for i in range(1, N + 1):
        # Rule: If the battery level is 1 or more just before traveling, the car can travel the section.
        # If it is less than 1, the car stops and cannot travel the current section.
        if curr_b < 1:
            print("No")
            return
        
        # After traveling section i, the battery level decreases by D_i.
        curr_b -= D[i-1]
        
        # Charging stations are positioned after section P_j.
        # If the current section i is a station position, Takahashi can choose to exchange the battery.
        if next_p is not None and i == next_p:
            # Exchange is optimal only if the station's battery level is higher than the current level.
            if next_s > curr_b:
                curr_b = next_s
            
            # Load the next available station's information
            if stations_left > 0:
                try:
                    next_p = int(next(it))
                    next_s = int(next(it))
                    stations_left -= 1
                except StopIteration:
                    next_p = None
                    next_s = None
                    stations_left = 0
            else:
                next_p = None
                next_s = None
    
    # If the loop completes, it means Takahashi traveled all sections successfully.
    print("Yes")

if __name__ == "__main__":
    solve()

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