概要

この問題は、毎日 \(D\) ミリリットルずつ水が蒸発する \(N\) 個の鉢植えに対して、青木君が最大 \(K\) 回（1日に最大1回）の「水量を0にするいたずら」を最適に行うとき、 \(M\) 日後に水量が \(1\) ミリリットル以上残る鉢植えの最小数を求める問題です。

---

考察

一見複雑なシミュレーションが必要そうに見えますが、鉢植え同士は互いに影響を与えないため、「それぞれの鉢植えが単体でどのように推移するか」に注目すると、非常にシンプルな規則性が見えてきます。

1. 青木君が何もしない場合に生き残る鉢植え

青木君が一切いたずらをしなかった場合、鉢植え \(i\) が \(M\) 日後に \(1\) ミリリットル以上残るための条件を考えます。 \(1\) 日に \(D\) ミリリットルずつ蒸発するため、 \(M\) 日間で合計 \(M \times D\) ミリリットルが蒸発します。 したがって、 \(M\) 日後に水量が \(1\) 以上残るためには、初期水量 \(A_i\) が以下の条件を満たす必要があります。

\[A_i - M \times D \ge 1 \iff A_i \ge M \times D + 1\]

この条件を満たさない鉢植え（ \(A_i < M \times D + 1\) ）は、青木君が何もしなくても勝手に水量が \(0\) になります。青木君は水量を最小化したいので、これらの鉢植えにいたずらをする必要はありません。

よって、青木君が狙うべきターゲットは、「放っておくと \(M\) 日後に \(1\) 以上残る鉢植え」（ \(A_i \ge M \times D + 1\) の鉢植え）だけです。このような鉢植えの総数を \(S\) とします。

2. 青木君ができるいたずらの最大回数

青木君はターゲットである \(S\) 個の鉢植えをできるだけ多く枯らそう（水量を \(0\) にしよう）とします。 青木君が \(M\) 日間で枯らすことができる鉢植えの最大数は、以下の制約によって決まります。

1. いたずらの上限回数: 合計で \(K\) 回までしかいたずらできません。
2. 日程の制約: 1日に1回しか行動できないため、 \(M\) 日間では最大 \(M\) 回しか行動できません。
3. ターゲットの数: そもそもターゲットとなる鉢植えは \(S\) 個しかありません（同じ鉢植えを複数回選ぶ意味はありません）。

これら3つの制約をすべて満たす必要があるため、青木君が枯らすことができる鉢植えの最大数は、これらの最小値である \(\min(S, M, K)\) 個となります。

3. 最終的に残る鉢植えの数

青木君は最適に行動するため、ターゲットとなる \(S\) 個の鉢植えのうち、ちょうど \(\min(S, M, K)\) 個を狙い撃ちして枯らします。 したがって、最終的に生き残る鉢植えの数は以下のように求まります。

\[\text{生き残る数} = S - \min(S, M, K)\]

---

アルゴリズム

1. 基準となる水量 \(\text{limit} = M \times D + 1\) を計算します。
2. 各鉢植えの初期水量 \(A_i\) を確認し、 \(A_i \ge \text{limit}\) を満たす鉢植えの数 \(S\) をカウントします。
3. 青木君が枯らせる鉢植えの数 \(\text{kill} = \min(S, M, K)\) を計算します。
4. 最終的な答え \(S - \text{kill}\) を出力します。

---

計算量

• 時間計算量: \(O(N)\) 各鉢植えの初期水量 \(A_i\) を1回ずつ走査して基準値と比較するため、鉢植えの数 \(N\) に対して線形時間で処理が完了します。\(N \le 10^6\) であるため、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\) 入力をすべて配列に格納して処理する場合、空間計算量は \(O(N)\) となります。

---

実装のポイント

• 高速な入出力: Pythonでは入力の数（最大 \(10^6\) 個）が多いため、input() を繰り返すのではなく、sys.stdin.read().split() を用いて一括で入力を取得することで実行時間を大幅に短縮できます。

• オーバーフローへの注意: \(M \le 10^9\) かつ \(D \le 10^9\) であるため、 \(\text{limit} = M \times D + 1\) は最大で \(10^{18} + 1\) になります。C++などの静的型付け言語を使用する場合は、32ビット整数型（int）ではなく、64ビット整数型（long long など）を使用する必要があります。Pythonでは自動的に多倍長整数として扱われるため、型を意識する必要はありません。

  ソースコード

import sys


def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    D = int(input_data[2])
    K = int(input_data[3])

    # いたずらがなくてもM日後に水量が1以上残るための最小初期水量
    limit = M * D + 1

    # 条件を満たす鉢植えの数をカウント
    S_count = 0
    for i in range(4, 4 + N):
        if int(input_data[i]) >= limit:
            S_count += 1

    # 青木君が0にできる鉢植えの最大数
    # 1日に1回しかいたずらできず、合計K回までなので、最大で min(M, K) 個
    kill = min(S_count, M, K)

    # 最終的に残る鉢植えの数
    ans = S_count - kill
    print(ans)


if __name__ == "__main__":
    solve()

---

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