概要

この問題は、蒸発と青木君のいたずらによって水が減っていく花壇において、最終的に水が \(1\text{ mL}\) 以上残る鉢植えの数を求める問題です。

一見すると複雑なシミュレーションが必要そうに見えますが、「蒸発だけで水がなくなってしまう鉢植え」と「青木君が妨害できる限界の回数」を整理することで、非常にシンプルな計算で答えを求めることができます。

考察

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

毎日 \(D\text{ mL}\) の水が \(M\) 日間蒸発するため、 \(M\) 日間で減少する水量は最大で \(M \times D\text{ mL}\) です。 青木君が一切いたずらをしなかった場合、鉢植え \(i\) に水が \(1\text{ mL}\) 以上残るための条件は以下のようになります。

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

この条件を満たす（＝放っておいても水が残る）鉢植えの個数を \(S\) とします。 逆に、 \(A_i \le M \times D\) である鉢植えは、青木君が何もしなくても蒸発だけで水が \(0\text{ mL}\) になってしまいます。

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

青木君の目的は、生き残る鉢植えの数を最小化することです。そのため、青木君は「放っておくと水が残る \(S\) 個の鉢植え」を優先的に狙って水を捨てます。

青木君がいたずらできる回数は、以下の2つの制約によって決まります。 - いたずらの最大回数は \(K\) 回である。 - いたずらは1日に1回しか行えず、期間は \(M\) 日間であるため、最大でも \(M\) 回しか行えない。

したがって、青木君が実際に水を \(0\) にできる鉢植えの最大個数は \(\min(K, M)\) 個となります。

3. 最適な行動をとった結果

青木君は、生き残る予定の \(S\) 個の鉢植えの中から、最大で \(\min(K, M)\) 個を選んで確実に枯らす（水量を \(0\) にする）ことができます。 したがって、最終的に生き残る鉢植えの数は、 \(S\) から青木君が潰した数を引いたものになります。

ただし、生き残る鉢植えの数は \(0\) 未満にはならないため、求める答えは以下のようになります。

\[\max(0, S - \min(K, M))\]

アルゴリズム

1. 各鉢植え \(i\) について、 \(A_i > M \times D\) を満たすか判定し、満たすものの個数 \(S\) をカウントします。
2. 青木君がアプローチできる最大回数 aoki_ops \(= \min(K, M)\) を計算します。
3. 最終的な答え \(\max(0, S - \text{aoki\_ops})\) を出力します。

計算量

• 時間計算量: \(O(N)\) 各鉢植えについて \(A_i > M \times D\) の判定を \(1\) 回ずつ行うため、 \(N\) に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 入力された \(A_i\) の値を格納するための配列のサイズが \(N\) となります。

実装のポイント

• オーバーフローの防止 制約より \(M \le 10^9\) 、 \(D \le 10^9\) であるため、 \(M \times D\) の値は最大で \(10^{18}\) に達します。 C++の通常の 64 ビット整数型（long long）では、掛け算の過程でオーバーフローが発生する危険があります。 そのため、正解コードでは 128 ビット整数型である __int128_t を使用して安全に比較を行っています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, M, D, K;
    if (!(cin >> N >> M >> D >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Use __int128_t to prevent overflow when multiplying M and D
    __int128_t loss = (__int128_t)M * D;

    long long S = 0;
    for (int i = 0; i < N; ++i) {
        if ((__int128_t)A[i] > loss) {
            S++;
        }
    }

    long long aoki_ops = min(K, M);
    long long ans = max(0LL, S - aoki_ops);

    cout << ans << "\n";

    return 0;
}

---

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