概要

各エクササイズを何回選べるかを数え上げ、合計で \(M\) 回のトレーニングが可能かを判定する問題です。

考察

1回のトレーニングでは、選んだエクササイズの残り回数が ちょうど \(K\) 減る ので、エクササイズ \(i\) を選べる回数は
- \(A_i \ge K\) の間だけ選べる - 選ぶたびに \(K\) ずつ減る

ということから、最大で [ \left\lfloor \frac{A_i}{K} \right\rfloor ] 回です。

ここで重要なのは、どの順番でエクササイズを選んでも「可能な総トレーニング回数」は変わらないことです。なぜなら、各エクササイズは独立に「\(K\) を何回引けるか」だけで上限回数が決まるからです。

素朴に「\(M\) 日ぶんを1日ずつシミュレーションする」方法は、\(M \le 10^9\) なので最悪 \(10^9\) 回の処理になり、時間的に間に合いません（TLEの原因）。

そこで、各 \(i\) について \(\left\lfloor A_i/K \right\rfloor\) を足し合わせ、その合計が \(M\) 以上かどうかだけを見ればよいです。

例えば \(K=3,\ A=[7,2,8]\) のとき - \(7//3=2\) 回 - \(2//3=0\) 回 - \(8//3=2\) 回
合計 \(4\) 回できるので、\(M \le 4\) なら Yes になります。

アルゴリズム

1. 入力として \(N,M,K\) と配列 \(A\) を受け取る。
2. カウンタ cnt=0 を用意する。
3. 各 \(a \in A\) について cnt += a // K を行う（そのエクササイズで可能な回数を加算）。
4. cnt >= M になった時点で Yes を出力して終了（早期終了）。
5. 最後まで足しても cnt < M なら No を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（※入力配列を除く。配列を保持するなら \(O(N)\)）

実装のポイント

• 可能回数は必ず整数なので、a // K（切り捨て除算）を使います。

• cnt が \(M\) に到達したら、それ以上計算する必要がないため早期終了すると高速です。

• \(A_i, K, M\) は最大 \(10^9\) ですが、合計は最大で \(N \times 10^9\) 程度になり得ます。Python の整数はオーバーフローしないので安心して加算できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = 0
    for a in A:
        cnt += a // K
        if cnt >= M:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

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