概要

\(Y\) 時間経過したあとに、電源が入っているスマートフォンの台数を最大化する問題です。最大 \(K\) 台までモバイルバッテリーでバッテリー消費を無効化できるため、どのスマートフォンをモバイルバッテリーに接続するかが鍵となります。

考察

まず、各スマートフォン \(i\) が \(Y\) 時間後に使用可能であるための条件を、モバイルバッテリーに「接続しない場合」と「接続する場合」で整理します。

1. モバイルバッテリーに接続しない場合 \(Y\) 時間後のバッテリー残量は \(A_i - Y\) % です。これが \(L\) % より大きければ使用可能です。 つまり、 \(A_i - Y > L \iff A_i > L + Y\) が条件です。
2. モバイルバッテリーに接続する場合 バッテリー残量は \(A_i\) % のまま維持されます。これが \(L\) % より大きければ使用可能です。 つまり、 \(A_i > L\) が条件です。

この条件をもとに、スマートフォンを以下の3つのタイプに分類します。

• タイプA (\(A_i > L + Y\)): モバイルバッテリーに接続しなくても、 \(Y\) 時間後に使用可能。
• タイプB (\(L < A_i \le L + Y\)): そのままでは \(Y\) 時間後に電源が切れるが、モバイルバッテリーに接続すれば使用可能になる。
• タイプC (\(A_i \le L\)): 現在すでに電源が切れているか、モバイルバッテリーに接続しても \(L\) % 以下であるため、 \(Y\) 時間後には必ず使用不可。

最大化の戦略として、モバイルバッテリーの枠 \(K\) は「接続することで結果が変わる」タイプBのスマートフォンに優先的に割り当てるのが最適です。タイプAは接続しなくてもカウントされ、タイプCは接続してもカウントされないためです。

アルゴリズム

1. タイプAのスマートフォンの個数 count_a と、タイプBのスマートフォンの個数 count_b を数えます。
2. タイプBのスマートフォンのうち、モバイルバッテリーで救済できるのは最大で \(K\) 台です。したがって、救済できる台数は \(\min(K, \text{count\_b})\) となります。
3. 最終的な答えは、 count_a（何もしなくても使える台数） + \(\min(K, \text{count\_b})\)（バッテリーで使えるようにした台数）となります。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のバッテリー残量を 1 回ずつ確認して分類するため、入力サイズに比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個のバッテリー残量をリストに保持する場合の計算量です。

実装のポイント

• 境界条件: 「 \(L\) % 以下になると電源が切れる」という条件から、使用可能であるためには「 \(L\) % より大きい（ \(A_i > L\) ）」必要がある点に注意してください。

• 無駄な接続: \(K\) が非常に大きい場合でも、タイプBの総数以上にモバイルバッテリーを使うメリットはありません。そのため min(k, count_b) を取る必要があります。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 各変数を整数としてパースします
    # N: スマートフォンの台数
    # L: バッテリー残量の閾値（L%以下で電源が切れる）
    # K: モバイルバッテリーに同時に接続できる最大台数
    # Y: 経過時間（時間）
    n = int(input_data[0])
    l = int(input_data[1])
    k = int(input_data[2])
    y = int(input_data[3])
    
    # 各スマートフォンの現在のバッテリー残量 A_i
    a = list(map(int, input_data[4:]))
    
    # スマートフォンが Y 時間後に使用可能であるための条件を考えます。
    # 1. モバイルバッテリーに接続しない場合：
    #    Y 時間後のバッテリー残量は A_i - Y % です。
    #    使用可能である条件は A_i - Y > L、つまり A_i > L + Y です。
    
    # 2. モバイルバッテリーに接続する場合：
    #    バッテリー残量は A_i % のまま維持されます。
    #    使用可能である条件は A_i > L です。
    
    # スマートフォンを以下の3つのタイプに分類します：
    # タイプA: A_i > L + Y
    #   モバイルバッテリーに接続しなくても Y 時間後に使用可能。
    # タイプB: L < A_i <= L + Y
    #   モバイルバッテリーに接続した場合のみ Y 時間後に使用可能。
    # タイプC: A_i <= L
    #   現在すでに電源が切れているか、接続しても L% 以下なので使用不可。
    
    count_a = 0
    count_b = 0
    
    threshold_a = l + y
    threshold_b = l
    
    for val in a:
        if val > threshold_a:
            count_a += 1
        elif val > threshold_b:
            count_b += 1
            
    # 使用可能なスマートフォンの数を最大化するには、
    # 接続枠 K を優先的にタイプBのスマートフォンに割り当てます。
    # タイプAは接続しなくてもカウントされ、タイプCは接続してもカウントされません。
    
    # タイプBのうち、救済できるのは最大で K 台です。
    saved_b = min(k, count_b)
    
    # 合計の最大台数は (タイプAの総数) + (救済したタイプBの数) となります。
    ans = count_a + saved_b
    
    # 結果を出力します
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。