概要

電気自動車が \(N\) 個の区間を走行する際、途中の充電ステーションでバッテリーを交換するかどうかを適切に選択し、全区間を走破できるか判定する問題です。

考察

重要な気づき

1. 充電ステーションでの選択は貪欲に決まる

   • バッテリーを交換すると残量が \(S_j\) になります
   • 現在の残量より \(S_j\) が大きければ交換した方が得、そうでなければ交換しない方が得です
   • なぜなら、バッテリー残量が多いほど先に進める可能性が高くなるからです

2. シミュレーションで十分

   • 区間を順番に走行しながら、充電ステーションがあれば交換を検討するだけでOK
   • 各区間を走行する前にバッテリー残量が \(1\) 以上あるか確認します

具体例で理解する

例えば \(N=3\)、\(K=5\)、\(D=[3, 4, 2]\) で、区間1と区間2の間（\(P=1\)）に \(S=6\) のステーションがある場合：

1. 区間1を走行: バッテリー \(5 \to 5-3=2\)
2. ステーション到着: 現在 \(2\) < \(S=6\) なので交換 → バッテリー \(6\)
3. 区間2を走行: バッテリー \(6 \to 6-4=2\)
4. 区間3を走行: バッテリー \(2 \to 2-2=0\)
5. 全区間走破成功！

なぜ貪欲法で正しいか

• 一度通り過ぎたステーションには戻れません
• 現在の残量より大きい \(S_j\) を持つステーションで交換しないと、その分の「お得さ」を失います
• 逆に、現在より小さい \(S_j\) に交換すると残量が減るだけで損です

アルゴリズム

1. 初期バッテリー残量を \(K\) に設定
2. 区間 \(1\) から \(N\) まで順番に処理：
   • 区間 \(i\) を走る前に、その手前にある充電ステーション（\(P_j = i-1\)）があれば確認
   • 現在のバッテリー残量より \(S_j\) が大きければ交換
   • 走行前にバッテリー残量が \(1\) 未満なら No を出力して終了
   • 区間を走行し、バッテリー残量を \(D_i\) だけ減らす
3. 全区間を走り終えたら Yes を出力

[スタート] --区間1--> [ステーション?] --区間2--> [ステーション?] --区間3--> [ゴール]
    K                  P=1にあれば         P=2にあれば

計算量

• 時間計算量: \(O(N + M)\)

  • 各区間を1回ずつ処理：\(O(N)\)
  • 各充電ステーションを1回ずつ確認：\(O(M)\)

• 空間計算量: \(O(N + M)\)

  • 配列 \(D\) の格納：\(O(N)\)
  • 充電ステーション情報の格納：\(O(M)\)

実装のポイント

1. インデックスの対応に注意

   • 問題文では区間は1-indexedですが、配列は0-indexedです
   • 「区間 \(i\) と区間 \(i+1\) の間」にあるステーションは、0-indexedで区間 \(i\) を走り終わった後に処理します

2. 走行の判定タイミング

   • 「走行する直前にバッテリー残量が \(1\) 以上」であれば走行可能
   • 走行後にバッテリーが \(0\) 以下になっても、次の区間の前に \(1\) 以上あれば問題ありません
   • 最後の区間を走り終えた後は、バッテリーが \(0\) 以下でもOKです

3. ステーションがない場合

   • \(M = 0\) の場合も正しく動作するよう、ループ内で station_idx < M のチェックを忘れずに

     ソースコード

def solve():
    N, M, K = map(int, input().split())
    D = list(map(int, input().split()))
    
    stations = []
    for _ in range(M):
        P, S = map(int, input().split())
        stations.append((P, S))
    
    # 現在のバッテリー残量
    battery = K
    
    # 充電ステーションのインデックス
    station_idx = 0
    
    for i in range(N):
        # 区間 i+1 を走行する前に充電ステーションがあるかチェック
        # 区間 i+1 の手前 = 区間 i と区間 i+1 の間
        # つまり P_j = i のとき、区間 i と区間 i+1 の間にステーションがある
        # 区間は1-indexedなので、区間 i+1 を走る前にチェックするのは P_j = i
        
        # i は 0-indexed で、区間番号は 1-indexed
        # 区間 i (0-indexed) を走る = 区間 i+1 (1-indexed) を走る
        # 区間 i+1 (1-indexed) の手前にあるステーションは P_j = i (1-indexed)
        
        # 区間 1 の手前にはステーションがないので、最初の区間の前はスキップ
        # 区間 i+1 (1-indexed) を走る前に、P_j = i の位置にあるステーションをチェック
        
        if i > 0:
            # 区間 i (1-indexed, つまり D[i-1]) を走り終わった後、
            # 区間 i+1 (1-indexed, つまり D[i]) を走る前
            # ステーション位置 P_j = i (1-indexed) をチェック
            while station_idx < M and stations[station_idx][0] == i:
                P, S = stations[station_idx]
                # バッテリーを交換するかどうか選択
                # 交換すると battery が S になる
                if S > battery:
                    battery = S
                station_idx += 1
        
        # 区間 i+1 (1-indexed) を走行
        # 走行前に battery >= 1 である必要がある
        if battery < 1:
            print("No")
            return
        
        # 走行後、バッテリーが D[i] 減少
        battery -= D[i]
        
        # バッテリーが 0 以下になっても、次の区間を走る前に 1 以上あればOK
        # ただし最後の区間を走り終わった後は関係ない
    
    # すべての区間を走行完了
    # 走行後にバッテリーが0以下でも、すべての区間を走り終えたのでOK
    print("Yes")

solve()

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