概要

各鉢植えについて「いたずらがなければ \(M\) 日後に水が残るか」を判定し、その中から青木君が最大で何個を潰せるかを引きます。

考察

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

1 日ごとに各鉢植えの水量は \(D\) 減るので、\(M\) 日後には合計で \(M \times D\) 減ります。
したがって、鉢植え \(i\) が \(M\) 日後に水量 \(1\) 以上で生き残る条件は、

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

です。これは整数なので、

\[ A_i > M \times D \]

と言い換えられます。

つまり、最初から \(A_i \leq M \times D\) の鉢植えは、青木君が何もしなくても \(M\) 日後には水がなくなります。

一方、\(A_i > M \times D\) の鉢植えは、青木君にいたずらされなければ生き残ります。
青木君は毎日の始まりに最大 1 回しか行動できないので、\(M\) 日間で実際に使えるいたずら回数は最大で \(M\) 回です。
また、合計回数の上限が \(K\) 回なので、実際に使える最大回数は

\[ \min(K, M) \]

回です。

青木君が最適に行動するなら、生き残る予定の鉢植えを優先して水量 \(0\) にします。
同じ鉢植えを複数回選ぶこともできますが、同じ鉢植えを何度も選んでも意味がないため、できるだけ異なる生き残り予定の鉢植えを狙います。

よって、いたずらがなければ生き残る鉢植えの数を survive とすると、答えは

\[ \max(0, \text{survive} - \min(K, M)) \]

です。

例えば、\(M=2, D=2\) のとき、合計で \(4\) 減ります。
初期水量が \([10, 5, 3]\) なら、\(4\) より大きい \(10, 5\) の 2 個だけが自然に生き残ります。
もし \(K=1\) なら青木君はそのうち 1 個を潰せるので、答えは \(1\) です。

素朴に \(M\) 日分のシミュレーションを行うと、\(M\) は最大 \(10^9\) なので間に合いません。
各鉢植えについて一度だけ判定すれば十分です。

アルゴリズム

1. \(M \times D\) を計算し、これを threshold とする。
2. 各鉢植えの初期水量 \(A_i\) について、\(A_i > \text{threshold}\) なら、いたずらがなければ生き残るので survive を 1 増やす。
3. 青木君が実際に使えるいたずら回数は min(K, M)。
4. 答えとして max(0, survive - min(K, M)) を出力する。

計算量

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

実装のポイント

\(M\) や \(D\) は最大 \(10^9\) なので、積 \(M \times D\) は最大 \(10^{18}\) になります。
int では収まらないため、long long を使う必要があります。

また、水量が \(1\) 以上残る条件は \(A_i \geq M \times D\) ではなく、\(A_i > M \times D\) であることに注意します。
ちょうど \(A_i = M \times D\) の場合、\(M\) 日後の水量は \(0\) になるため生き残りません。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, M, D, K;
    cin >> N >> M >> D >> K;

    long long threshold = M * D;
    long long survive = 0;

    for (int i = 0; i < N; i++) {
        long long A;
        cin >> A;
        if (A > threshold) survive++;
    }

    long long attacks = min(K, M);
    cout << max(0LL, survive - attacks) << '\n';

    return 0;
}

---

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