概要

\(M\) 日間の蒸発後に生き残る鉢植え（水量 \(\geq 1\) ml）の数を求める問題。青木君は最適に行動して生存数を最小化する。

考察

蒸発だけを考える

まず青木君のいたずらがない場合を考えます。\(M\) 日後の鉢植え \(i\) の水量は \(\max(0, A_i - M \cdot D)\) です。

よって、\(M\) 日後に水量が \(1\) 以上残る条件は：

\[A_i - M \cdot D \geq 1 \iff A_i \geq M \cdot D + 1\]

これを閾値 \(T = M \cdot D + 1\) とおき、\(A_i \geq T\) を満たす鉢植えの数を \(S\) とします。

青木君のいたずらの効果

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

同じ鉢植えに複数回行動する必要はありません（1回で水量が \(0\) になり、復活しないため）。

青木君の最適戦略

青木君が狙うべきは「放置すれば生き残る鉢植え」（\(A_i \geq T\) のもの）です。既に枯れる運命の鉢植えを狙っても無意味だからです。

青木君は1日に1回しか行動できず、全 \(M\) 日間で行動可能です。さらに合計 \(K\) 回までという制限があるため、実際に行動できる回数は \(\min(K, M)\) 回です。

結論

生き残る鉢植えの数は：

\[\text{answer} = \max(0,\ S - \min(K, M))\]

アルゴリズム

1. 閾値 \(T = M \times D + 1\) を計算する
2. \(A_i \geq T\) を満たす鉢植えの数 \(S\) を数える
3. 青木君の有効行動回数 \(\min(K, M)\) を計算する
4. \(\max(0, S - \min(K, M))\) を出力する

具体例

\(N=5,\ M=3,\ D=2,\ K=1,\ A = [10, 5, 8, 3, 7]\) の場合：

• 閾値 \(T = 3 \times 2 + 1 = 7\)
• \(A_i \geq 7\) を満たすのは \(A_1=10, A_3=8, A_5=7\) の \(3\) 個 → \(S=3\)
• 有効行動回数 \(= \min(1, 3) = 1\)
• 答え \(= \max(0, 3 - 1) = 2\)

計算量

• 時間計算量: \(O(N)\)（各鉢植えを1回走査するだけ）
• 空間計算量: \(O(1)\)（配列を保持せず逐次処理）

実装のポイント

• オーバーフロー対策: \(M \times D\) は最大 \(10^9 \times 10^9 = 10^{18}\) になるため、long long を使用する必要があります。閾値 \(T = M \cdot D + 1\) も long long の範囲内に収まります（最大約 \(10^{18} + 1\)）。

• \(K\) と \(M\) の最小値: 青木君は1日1回しか行動できないため、\(K > M\) の場合でも実際には \(M\) 回しか行動できません。この制約を忘れると WA になります。

• 入力の高速化: \(N\) が最大 \(10^6\) なので、ios_base::sync_with_stdio(false) と cin.tie(NULL) で入力を高速化しています。

  ソースコード

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, M, D, K;
    cin >> N >> M >> D >> K;
    
    long long threshold = M * D + 1;
    
    long long S = 0;
    for (long long i = 0; i < N; i++) {
        long long A;
        cin >> A;
        if (A >= threshold) {
            S++;
        }
    }
    
    long long effective_K = min(K, M);
    long long answer = max(0LL, S - effective_K);
    
    cout << answer << endl;
    
    return 0;
}

---

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