概要

\(N\) 台の中古車の中から、価格が指定範囲内かつ走行距離が上限以下という条件を満たす車の台数を数える問題です。

考察

この問題では、各車について以下の2つの条件を同時に満たすかどうかを判定します：

1. 価格の条件: \(L \leq P_i \leq R\)（価格が \(L\) 万円以上 \(R\) 万円以下）
2. 走行距離の条件: \(K_i \leq M\)（走行距離が \(M\) km 以下）

例えば、\(L = 50\), \(R = 100\), \(M = 30000\) のとき： - 価格 60 万円、走行距離 25000 km の車 → 候補車（両方の条件を満たす） - 価格 40 万円、走行距離 20000 km の車 → 候補車ではない（価格が安すぎる） - 価格 80 万円、走行距離 50000 km の車 → 候補車ではない（走行距離が長すぎる）

この問題は単純な条件判定の繰り返しなので、各車を1台ずつ順番にチェックしていく全探索で十分解けます。\(N \leq 10^5\) という制約に対して、1台あたり \(O(1)\) で判定できるため、時間制限内に収まります。

アルゴリズム

1. カウンタ変数 count を \(0\) で初期化する
2. \(N\) 台の車それぞれについて、価格 \(P_i\) と走行距離 \(K_i\) を読み込む
3. 各車について、\(L \leq P_i \leq R\) かつ \(K_i \leq M\) を満たすかチェックする
4. 条件を満たす場合、count を \(1\) 増やす
5. 最後に count を出力する

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 台の車それぞれに対して、定数時間 \(O(1)\) で条件判定を行うため
• 空間計算量: \(O(1)\)
  • カウンタ変数と、現在読み込んでいる車の情報のみを保持するため

実装のポイント

• Pythonでは L <= P <= R という書き方で「\(L\) 以上 \(R\) 以下」を簡潔に表現できます。これは L <= P and P <= R と同じ意味です。

• 条件を満たすかどうかの判定は and で2つの条件を結合します。両方とも True のときのみ全体が True になります。

• 各車の情報は一度使ったら不要になるため、リストに保存せず、読み込みながら直接判定することでメモリを節約しています。

  ソースコード

N, L, R, M = map(int, input().split())
count = 0
for _ in range(N):
    P, K = map(int, input().split())
    if L <= P <= R and K <= M:
        count += 1
print(count)

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