概要

\(Y\) 時間後に電源が入っているスマホの台数を最大化するために、「何もしなくても生き残るスマホ」と「モバイルバッテリーに繋げば生き残るスマホ」を数え上げて答えを求めます。

考察

まず、モバイルバッテリーに接続したスマホは 一切減らない ので、\(Y\) 時間後も「今この瞬間に電源が切れていなければ」確実に使用可能です。
一方、接続しないスマホは毎時間 \(1\%\) ずつ減るため、\(Y\) 時間後にはバッテリーが \(A_i - Y\) になります。

ここで注意すべきなのが「\(L\%\) ちょうどになった瞬間に電源が切れる」点です。
つまり \(Y\) 時間後に使用可能である条件は - 接続しない場合：\(A_i - Y > L\)（\(=\) だとその瞬間に切れる） - 接続する場合：減らないので \(A_i > L\)（今すでに \(L\) 以下なら既に使えない）

したがって各スマホは次の3種類に分類できます：

1. 何もしなくても生き残る
   \(A_i > L + Y\)
   → 接続不要で \(Y\) 時間後も使用可能

2. 接続すれば生き残る
   \(L < A_i \le L + Y\)
   → 接続しないと途中で \(L\) 以下になって落ちるが、接続すれば減らないので使用可能

3. どうやっても無理
   \(A_i \le L\)
   → 今この瞬間に使用不可（接続しても復活しない）

よって最適戦略は単純で、(2) のスマホを「最大 \(K\) 台まで」接続して救うのが最善です。
(1) は最初から助かっていて、(3) は助けられません。

素朴に「どれを繋ぐか」を探索したりソートしてシミュレーションする必要はなく、条件判定で数えるだけで答えが出ます。

例：\(L=20, Y=5\) のとき
- \(A_i \ge 26\)（\(>25\)）なら未接続でも生存
- \(21 \sim 25\) は接続すれば生存
- \(20\) 以下は不可

アルゴリズム

1. \(threshold = L + Y\) を計算する
2. 全スマホについて以下を数える
   • survive: \(A_i > threshold\) の個数（未接続でも生存）
   • need: \(L < A_i \le threshold\) の個数（接続すれば生存）
3. 答えは
   $\(survive + \min(K, need)\)\( （救える台数はポート数 \)K$ を超えない）

計算量

• 時間計算量: \(O(N)\)（1回なめるだけ）
• 空間計算量: \(O(1)\)（カウンタのみ、入力配列を除く）

実装のポイント

• 「ちょうど \(L\%\) で電源が切れる」ため、生存条件は \(>\)（厳密不等号） になる点に注意します。

  • 未接続の生存条件：\(A_i > L + Y\)
  • 接続可能（今生きている）条件：\(A_i > L\)

• 答えは survive + min(K, need) の1行で確定します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, L, K, Y = map(int, input().split())
    A = list(map(int, input().split()))

    survive = 0
    need = 0
    threshold = L + Y

    for a in A:
        if a > threshold:
            survive += 1
        elif a > L:
            need += 1

    print(survive + min(K, need))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。