概要

各エクササイズの残り回数から、1日1回のトレーニングをM日間続けられるか判定する問題です。1回のトレーニングではK回分の回数を消費します。

考察

各エクササイズiについて、最大で何回トレーニングに使用できるかを考えます。エクササイズiの残り回数がA_i回の場合、このエクササイズをトレーニングに使用できる最大回数はfloor(A_i/K)回です（ただし最大M回まで）。なぜなら、1回のトレーニングでK回分消費するため、A_i回分の残りでは最大でA_i//K回しか使用できないからです。

すべてのエクササイズから得られるトレーニング回数の合計がM以上であれば、M日間のトレーニングを達成できます。逆に合計がM未満であれば達成できません。

アルゴリズム

1. 各エクササイズiについて、使用可能なトレーニング回数を計算: min(A_i // K, M)
2. すべてのエクササイズの使用可能回数を合計する
3. 合計値がM以上なら”Yes”、そうでなければ”No”を出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 各エクササイズの使用可能回数を計算する際、min関数でMを上限とすることで、必要以上の計算を防いでいます

• 入力値が大きい場合（最大\(2 \times 10^5\)要素）を考慮し、効率的なループ処理を行っています

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:3+n]))
    
    total_possible = 0
    for a in A:
        total_possible += min(a // K, M)
    
    if total_possible >= M:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。