概要

\(M\) 日間の蒸発に耐えられる鉢植えの数を求め、そこから青木君が最適に行動して枯らせる鉢植えの数を引く問題です。

考察

蒸発による自然淘汰

まず、青木君のいたずらがない場合を考えます。\(M\) 日後、鉢植え \(i\) の水量は \(\max(0, A_i - M \times D)\) になります。水量が \(1\) ミリリットル以上残る条件は：

\[A_i - M \times D \geq 1 \iff A_i > M \times D\]

つまり、初期水量が閾値 \(M \times D\) を超える鉢植えだけが自然に生き残ります。

青木君のいたずらの効果

青木君が鉢植えの水量を \(0\) にすると、その後蒸発しても水量は \(0\) のままなので、1回の行動で確実に1つの鉢植えを枯らすことができます。

青木君は最適に行動するので、自然に生き残る鉢植えだけを狙います（既に枯れる予定の鉢植えを狙っても無駄）。

行動回数の制約

青木君は「毎日の始まりに \(1\) 回だけ」行動できるため、\(M\) 日間で最大 \(M\) 回しか行動できません。上限 \(K\) 回と合わせて、実際に行動できる回数は \(\min(K, M)\) 回です。

具体例

\(N=5, M=3, D=2, K=2, A = [10, 5, 7, 3, 20]\) の場合： - 閾値 = \(3 \times 2 = 6\) - \(A_i > 6\) を満たすのは \(A_1=10, A_3=7, A_5=20\) の 3個 - 青木君の有効行動回数 = \(\min(2, 3) = 2\) - 答え = \(\max(0, 3 - 2) = 1\)

アルゴリズム

1. 閾値 \(\text{threshold} = M \times D\) を計算する
2. \(A_i > \text{threshold}\) を満たす鉢植えの数（count_surviving）を数える
3. 青木君の有効行動回数を \(\text{effective\_K} = \min(K, M)\) とする
4. 答えは \(\max(0, \text{count\_surviving} - \text{effective\_K})\)

計算量

• 時間計算量: \(O(N)\) — 全鉢植えを1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の読み込み分（逐次読みなら \(O(1)\) も可能）

実装のポイント

• \(M \times D\) のオーバーフローに注意。\(M, D\) がともに最大 \(10^9\) なので、積は最大 \(10^{18}\) になります。Python では整数のオーバーフローがないため問題ありませんが、C++ などでは long long が必要です。

• sys.stdin.buffer.read() で一括読み込みすることで、\(N\) が最大 \(10^6\) の場合でも高速に入力を処理できます。

• 青木君の行動回数の上限が \(K\) だけでなく \(M\)（日数）にも制限されることを見落とさないようにしましょう。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    M = int(data[1])
    D = int(data[2])
    K = int(data[3])
    
    threshold = M * D
    
    count_surviving = 0
    for i in range(4, 4 + N):
        if int(data[i]) > threshold:
            count_surviving += 1
    
    effective_K = min(K, M)
    
    answer = max(0, count_surviving - effective_K)
    print(answer)

main()

---

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