概要

各エクササイズを何回トレーニングに使えるかを合計し、それが \(M\) 以上かどうかを判定する問題です。

考察

重要な気づき

1日のトレーニングでは、1つのエクササイズを選び、その残り回数をちょうど \(K\) 減らします。つまり、エクササイズ \(i\) は最大で \(\lfloor A_i / K \rfloor\) 回（\(A_i\) を \(K\) で割った商）だけトレーニングに使えます。

例えば、\(K = 3\) のとき： - \(A_i = 10\) なら \(\lfloor 10 / 3 \rfloor = 3\) 回使える（残り回数は \(10 \to 7 \to 4 \to 1\) と減る） - \(A_i = 6\) なら \(\lfloor 6 / 3 \rfloor = 2\) 回使える - \(A_i = 2\) なら \(\lfloor 2 / 3 \rfloor = 0\) 回（\(K\) 未満なので一度も選べない）

どのエクササイズを何日目に選ぶかは関係ない

毎日1つエクササイズを選ぶだけなので、順番は自由です。重要なのは 全エクササイズで合計何回トレーニングできるか だけです。

すべてのエクササイズについて \(\lfloor A_i / K \rfloor\) を合計した値が、\(M\) 日間のトレーニングに足りるかどうかを確認すればよいです。

素朴なシミュレーションが危険な理由

\(M\) は最大 \(10^9\) なので、1日ずつシミュレーションすると \(O(M)\) となり TLE になります。しかし、上記の考察により各エクササイズの使用可能回数を割り算で直接求められるため、シミュレーションは不要です。

アルゴリズム

1. 各エクササイズ \(i\) について、\(\lfloor A_i / K \rfloor\) を計算する。
2. それらをすべて合計し、\(\text{total}\) とする。
3. \(\text{total} \geq M\) ならば Yes、そうでなければ No を出力する。

具体例（入力: \(N=3, M=5, K=3, A=[10, 6, 2]\)）

エクササイズ	\(A_i\)	\(\lfloor A_i / K \rfloor\)
1	10	3
2	6	2
3	2	0

合計 \(= 3 + 2 + 0 = 5 \geq 5\) なので Yes。

計算量

• 時間計算量: \(O(N)\)（各エクササイズについて割り算を1回行い、合計を求める）
• 空間計算量: \(O(N)\)（配列 \(A\) の格納）

実装のポイント

• \(M\) や \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、合計値は最大で約 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローを気にする必要はありませんが、C++ などで実装する場合は long long 型を使う必要があります。

• Python の // 演算子は切り捨て除算を行うため、\(\lfloor A_i / K \rfloor\) をそのまま計算できます。

  ソースコード

N, M, K = map(int, input().split())
A = list(map(int, input().split()))

total = sum(a // K for a in A)
print("Yes" if total >= M else "No")

---

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