概要

\(N\) 台のスマートフォンのうち、\(Y\) 時間後にまだ使える台数を最大化するために、最大 \(K\) 台までモバイルバッテリーに接続するとき、その最大値を求めよ。

考察

まず、各スマートフォンのバッテリー残量 \(A_i\) と、\(Y\) 時間後の消費量 \(Y\)%、そして電源が切れる閾値 \(L\)% の関係を考えます。

• モバイルバッテリーを使わなければ、\(Y\) 時間後に使える条件は
  $\(A_i - Y > L\)\( つまり、 \)\(A_i > L + Y\)$
  を満たすこと。

この条件を満たすスマホは、モバイルバッテリーがなくても生き残れます。

一方、
$\(L < A_i \leq L + Y\)\( を満たすスマホは、そのままでは \)Y$ 時間後にバッテリーが足りなくなって使えなくなるため、モバイルバッテリーを使って「救う」価値があります。

逆に、
$\(A_i \leq L\)$
であるようなスマホは、すでにバッテリーが少ないので、最初から使えないかすぐに切れるため、モバイルバッテリーを使っても意味がありません。

したがって、戦略としては：

1. 最初から \(A_i > L + Y\) であるスマホは自動的に生き残るのでカウント。
2. \(L < A_i \leq L + Y\) であるスマホの中から、多くとも \(K\) 台をモバイルバッテリーで「救う」。
3. 救えるのは最大 \(K\) 台なので、この範囲にあるスマホをバッテリーが多い順にソートして上位 \(K\) 台を選ぶのが最適。

このように分類することで、全探索せずに効率的に答えを求めることができます。

アルゴリズム

1. 入力を受け取る。
2. \(A_i > L + Y\) を満たすスマホの数を数える（survive_without_powerbank）。
3. \(L < A_i \leq L + Y\) を満たすスマホをリストアップし、降順にソートする。
4. 上記リストの上位最大 \(K\) 台を「救える」としてカウントする。
5. 2と4の合計が答え。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが必要なため）
• 空間計算量: \(O(N)\)（リスト can_be_saved のサイズ）

実装のポイント

• リスト内包表記を使って条件に合う要素を抽出するのが簡潔。
• ソートは降順に行い、「より多く残る可能性のあるスマホ」を優先的にモバイルバッテリーで使う。
• min(K, len(can_be_saved)) で、実際に救える数を正確に計算すること。

## ソースコード

```python
import heapq

N, L, K, Y = map(int, input().split())
A = list(map(int, input().split()))

# モバイルバッテリーを使わない場合、Y時間後に使える条件は A[i] > L + Y
# しかし、モバイルバッテリーをK台まで接続できるので、それを利用して最適化する

# 各スマホについて、Y時間後に使えるかどうかを判定
# モバイルバッテリーを使っても使わなくても、バッテリーがL以下になると切れる
# モバイルバッテリーを使っていないスマホはY時間後に A[i] - Y > L であればよい
# つまり A[i] > L + Y

# モバイルバッテリーを使うことで無限に使えるようになるので、
# モバイルバッテリーを使うべきは、Y時間後に自然に切れてしまうスマホ

# まず、モバイルバッテリーを使わずにY時間後に生き残るスマホの数を数える
survive_without_powerbank = sum(1 for a in A if a > L + Y)

# モバイルバッテリーを使ってY時間後に生き残れるスマホの数を調べる
# 条件：A[i] > L （そうでないと最初から使えない or すぐに切れる）
# そして、A[i] <= L + Y （すでに生き残れるならモバイルバッテリー不要）

can_be_saved = [a for a in A if L < a <= L + Y]
can_be_saved.sort(reverse=True)  # 大きい順（バッテリーが多いものを優先的に救う）

# モバイルバッテリーで救えるのは最大K台
saved_by_powerbank = min(K, len(can_be_saved))

# 結果：自然に生き残るスマホ + モバイルバッテリーで救えるスマホ
result = survive_without_powerbank + saved_by_powerbank
print(result)

この解説は qwen3-coder-480b によって生成されました。