概要

落葉の総数は \(A \times B\) 枚です。1 日に最大 \(C\) 枚ずつ掃除する様子をシミュレーションし、\(D\) 日以内にすべて掃除できるかを判定します。

考察

できるだけ早く掃除を終えるには、毎日、残っている落葉を最大 \(C\) 枚まで掃除すればよいです。

そこで、落葉の残り枚数を leaves とし、最初に \(A \times B\) を代入します。1 日掃除するたびに leaves から \(C\) を引き、残りが \(0\) 以下になったら、すべて掃除できたと判断します。

例えば、\(A=3,\ B=5,\ C=4,\ D=4\) の場合、落葉は全部で \(15\) 枚です。残り枚数は次のように変化します。

• 1 日後：\(11\)
• 2 日後：\(7\)
• 3 日後：\(3\)
• 4 日後：\(-1\)

実際には最後の日に残りの \(3\) 枚だけを掃除しますが、コードでは一律に \(C\) を引いています。そのため、残り枚数が負になった場合も掃除完了として扱います。

この問題では \(D \leq 1000\) なので、1 日ずつシミュレーションする素朴な方法で十分間に合います。ただし、掃除完了の条件を「残りがちょうど \(0\)」としてしまうと、上の例で誤答するため注意が必要です。

なお、\(D\) 日間に掃除できる最大枚数は \(C \times D\) なので、\(A \times B \leq C \times D\) を直接判定する方法もあります。提示されたコードでは、日ごとのシミュレーションを行っています。

アルゴリズム

1. \(A,B,C,D\) を読み込む。
2. 落葉の残り枚数 leaves を \(A \times B\) にする。
3. 次の両方を満たす間、leaves から \(C\) を引き、経過日数を 1 増やす。
   • 経過日数が \(D\) 未満である。
   • leaves が \(0\) より大きい。
4. leaves が \(0\) 以下なら Yes、そうでなければ No を出力する。

毎日最大限掃除しても \(D\) 日後に落葉が残る場合、それより少なく掃除しても終わらないため、この判定で正しい答えが得られます。

計算量

• 時間計算量: \(O(D)\)。最大 \(D\) 回の繰り返しを行います。
• 空間計算量: \(O(1)\)。固定個数の変数のみを使用します。

実装のポイント

• 掃除完了の判定は leaves == 0 ではなく、leaves <= 0 にします。

• 途中で掃除が完了したら、それ以降のシミュレーションは不要です。ループ条件の leaves > 0 によって早めに終了します。

• day を \(0\) から始め、day < d とすることで、掃除を行う回数を最大 \(D\) 回にします。

• 出力は指定どおり、大文字・小文字を区別して Yes または No とします。

  ソースコード

// 問題文から独立に実装: 1 日ずつ掃除して残りが 0 以下になるか
#include <iostream>
int main() {
    long long a, b, c, d; std::cin >> a >> b >> c >> d;
    long long leaves = a * b;
    for (int day = 0; day < d && leaves > 0; ++day) leaves -= c;
    std::cout << (leaves <= 0 ? "Yes" : "No") << std::endl;
}

---

この解説は gpt-6-astra-medium によって生成されました。