概要

\(N\) 台のスマートフォンのうち、モバイルバッテリーを最適に割り当てて、\(Y\) 時間後に使用可能な台数を最大化する問題です。各スマートフォンを「既に使えない」「放置しても生き残る」「充電しないと死ぬ」の3カテゴリに分類して貪欲に解きます。

考察

バッテリーの減り方と電源が切れる条件

• スマートフォンは毎時間 \(1\)% ずつバッテリーが減るため、\(Y\) 時間後のバッテリー残量は \(A_i - Y\)（%）になります。
• バッテリー残量が \(L\)% 以下になった瞬間に電源が切れます。つまり、生存条件は「バッテリー残量が \(L\) より厳密に大きい」ことです。

スマートフォンの3つのカテゴリ

各スマートフォンを以下の3グループに分類できます：

1. 既に使えない（\(A_i \leq L\)）：現時点でバッテリーが \(L\)% 以下なので、モバイルバッテリーを繋いでも復活しません。救済不可能です。

2. 放置しても生き残る（\(A_i > L + Y\)）：\(Y\) 時間後のバッテリー残量は \(A_i - Y > L\) なので、充電しなくても生存します。モバイルバッテリーを使う必要がありません。

3. 充電しないと死ぬ（\(L < A_i \leq L + Y\)）：現在は生きていますが、\(Y\) 時間後には \(A_i - Y \leq L\) となり電源が切れます。モバイルバッテリーに接続すれば救えます。

貪欲な戦略

具体例で考えます。\(N=5, L=10, K=2, Y=5, A = [20, 8, 16, 12, 30]\) の場合：

• \(A_2 = 8 \leq 10 = L\)：既に死んでいる
• \(A_5 = 30 > 15 = L+Y\)：放置で生存
• \(A_1 = 20 > 15\)：放置で生存
• \(A_3 = 16 > 15\)：放置で生存
• \(A_4 = 12\)：\(10 < 12 \leq 15\) なので、充電が必要

カテゴリ3のスマートフォンは1台で、\(K=2\) なので全て救えます。答えは \(3 + 1 = 4\) 台です。

モバイルバッテリーはカテゴリ3の端末に優先的に割り当てるのが最適です。カテゴリ2には不要で、カテゴリ1は救えないからです。

アルゴリズム

1. 各スマートフォンについて3カテゴリに分類する
2. カテゴリ2（放置で生存）の台数を数える → \(S\)
3. カテゴリ3（充電が必要）の台数を数える → \(C\)
4. モバイルバッテリーで救える台数は \(\min(K, C)\) 台
5. 答えは \(S + \min(K, C)\)

計算量

• 時間計算量: \(O(N)\)（各スマートフォンを1回ずつ確認するだけ）
• 空間計算量: \(O(N)\)（入力の格納）

実装のポイント

• 生存条件の境界に注意：「\(L\)% 以下で電源が切れる」ので、生存は「\(> L\)」です。\(\geq L\) ではなく \(> L\) であることに気をつけましょう。

• 既に死んでいるスマートフォンの除外：\(A_i \leq L\) の端末はモバイルバッテリーを繋いでも復活しないため、最初に除外する必要があります。

• \(K\) がカテゴリ3の台数より多い場合：余ったポートをカテゴリ2に繋いでも効果はないので、\(\min(K, C)\) で上限を取ります。

  ソースコード

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

# Each phone loses Y% over Y hours (1% per hour)
# Phone dies when battery <= L (exactly L means it dies)
# So phone i survives without charging if A_i - Y > L, i.e., A_i - Y >= L + 1, i.e., A_i > L + Y
# Phone connected to mobile battery never loses charge, so it survives as long as A_i > L
# Wait: "バッテリー残量がL%以下になると電源が切れて使えなくなります"
# Current battery is A_i. If A_i <= L already, phone is already dead even if connected?
# Actually, "ちょうどL%になった瞬間に電源が切れます" - so at L% it dies.
# If A_i > L, connecting to mobile battery keeps it alive (no consumption).
# If A_i <= L, the phone is already dead or dies at L%.
# Wait, A_i could be > L currently. Let me re-read.
# "バッテリー残量がL%以下になると電源が切れる" and "ちょうどL%になった瞬間に電源が切れる"
# So the phone dies when battery reaches L%. If A_i > L, it's currently alive.
# If A_i == L or A_i < L... but A_i >= 1 and L can be 0..99.
# If A_i <= L, the phone is already at or below L%, so it's already dead.

# Categories:
# 1. Already dead (A_i <= L): can't be saved, count = 0
# 2. Alive and survives without charging: A_i - Y > L, i.e., A_i > L + Y (after Y hours, battery = A_i - Y > L)
#    Wait: dies when reaching L, so survives if A_i - Y > L, i.e., A_i > L + Y
#    Actually: "L%以下になると電源が切れる" means <= L dies. So survives if battery > L after Y hours.
#    After Y hours: A_i - Y. Survives if A_i - Y > L, i.e., A_i > L + Y.
# 3. Alive but will die without charging: A_i > L but A_i <= L + Y
#    These need mobile battery to survive.

# Strategy: 
# - Phones with A_i <= L: dead, nothing to do
# - Phones with A_i > L + Y: survive without mobile battery
# - Phones with L < A_i <= L + Y: need mobile battery to survive
# We should connect mobile battery to as many of category 3 as possible (up to K).
# If K > number of category 3 phones, extra connections don't help (category 2 already survives).

alive = [a for a in A if a > L]
survive_without = sum(1 for a in alive if a > L + Y)
need_charging = sum(1 for a in alive if a <= L + Y)

charged = min(K, need_charging)
print(survive_without + charged)

---

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