概要

各鉢植えが、何もしなくても \(M\) 日後に水が残るかを判定し、そのうち青木君のいたずらで何個減らされるかを考えます。

考察

まず、いたずらがない場合を考えます。

鉢植え \(i\) の水量は、\(M\) 日間で合計 \(M \times D\) ミリリットル減ります。
したがって、\(M\) 日後に水が \(1\) ミリリットル以上残る条件は

\[ A_i > M \times D \]

です。

\(A_i = M \times D\) の場合はちょうど \(0\) になるため、生き残りません。

次に、青木君のいたずらについて考えます。

青木君は毎日の始まりに最大 \(1\) 回、鉢植えを \(0\) にできます。
一度 \(0\) にされた鉢植えは、その後水が補充されないため、最終的に水が残ることはありません。

つまり、青木君のいたずら \(1\) 回で、「本来なら生き残る鉢植え」を最大 \(1\) 個減らせます。

ただし、青木君が行動できるのは \(M\) 日間で最大 \(1\) 回ずつなので、実際に使えるいたずら回数は

\[ \min(K, M) \]

回です。

例えば、本来生き残る鉢植えが \(5\) 個あり、青木君が \(3\) 回いたずらできるなら、最終的に残るのは

\[ 5 - 3 = 2 \]

個です。

一方で、本来生き残る鉢植えが \(2\) 個しかないのに、青木君が \(5\) 回いたずらできても、残る数は負にはならず \(0\) 個です。

素朴に \(M\) 日分の蒸発をシミュレーションすると、\(M\) は最大 \(10^9\) なので到底間に合いません。
また、どの日にどの鉢植えを攻撃するかを細かく考える必要もありません。最終的には「本来生き残る鉢植えを何個潰せるか」だけが重要です。

アルゴリズム

1. \(threshold = M \times D\) を計算する。
2. 各鉢植えについて、\(A_i > threshold\) なら本来生き残るので数える。
3. 青木君が有効に使えるいたずら回数を $\( attacks = \min(K, M) \)$ とする。
4. 答えは $\( \max(0, survive - attacks) \)$ である。

ここで、\(survive\) はいたずらがない場合に生き残る鉢植えの数です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

入力を一括で読み込んでいるため、実装上の空間計算量は \(O(N)\) です。
逐次的に読み込む実装にすれば、追加の空間計算量は \(O(1)\) にできます。

実装のポイント

\(M\) と \(D\) は最大 \(10^9\) なので、\(M \times D\) は最大 \(10^{18}\) になります。
Python では整数の桁あふれを気にする必要はありませんが、他の言語では 64 bit 整数型を使う必要があります。

また、生き残る条件は \(A_i \geq M \times D\) ではなく、

\[ A_i > M \times D \]

であることに注意します。
ちょうど \(M \times D\) の場合、最終的な水量は \(0\) になるためです。

ソースコード

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
    survive = 0

    for x in data[4:]:
        if int(x) > threshold:
            survive += 1

    attacks = K if K < M else M
    ans = survive - attacks
    if ans < 0:
        ans = 0

    print(ans)

if __name__ == "__main__":
    main()

---

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