概要

\(N\) 種類のエクササイズがあり、それぞれ \(A_i\) 回分行えます。1回のトレーニングでいずれか1つのエクササイズを \(K\) 回分消化するとき、合計 \(M\) 回のトレーニングが可能かどうかを判定する問題です。

考察

この問題のポイントは、「各エクササイズが最大で何回のトレーニングに貢献できるか」を独立に考えられる点です。

あるエクササイズ \(i\) の残り回数が \(A_i\) であるとき、1回のトレーニングで \(K\) 回分を消費します。このエクササイズから最大で何回のトレーニングを行えるかを考えると、以下のようになります。 - \(A_i < K\) のとき： 0回 - \(A_i \geq K\) のとき： \(\lfloor A_i / K \rfloor\) 回（\(A_i\) を \(K\) で割った商）

例えば、\(A_i = 10, K = 3\) の場合、このエクササイズを使って \(10 \div 3 = 3\) 余り \(1\) となるため、最大 3 回のトレーニングが可能です。余った 1 回分は \(K\) 未満であるため、他のトレーニングに回すことはできません。

高橋君が合計 \(M\) 回のトレーニングを行いたい場合、すべての種類のエクササイズから得られる「可能なトレーニング回数」の合計が \(M\) 以上であれば、目標を達成できることになります。

アルゴリズム

1. 合計可能回数を保持する変数 total_possible_sessions を \(0\) で初期化します。
2. 各エクササイズ \(i = 1, 2, \ldots, N\) について以下を繰り返します：
   • \(A_i\) を \(K\) で割った商（切り捨て）を計算し、total_possible_sessions に加算します。
3. 最終的な total_possible_sessions が \(M\) 以上であれば Yes を、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N)\)
  • エクササイズの数 \(N\) に対して 1 回ずつループを回して計算を行うため、線形時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) をリスト等に保持する場合に \(O(N)\) 必要です。入力を 1 つずつ読み込んで処理する場合は \(O(1)\) に抑えることも可能です。

実装のポイント

• 大きな数値への対応: \(M, K, A_i\) の値は最大 \(10^9\) と非常に大きくなりますが、Python などの言語では標準で多倍長整数が扱えるため、オーバーフローを気にせず計算できます。

• 整数の割り算: \(A_i / K\) の計算では、小数点以下を切り捨てた整数値（商）を求める必要があります。Python では // 演算子を使うことで簡潔に記述できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目の N, M, K を取得します
    # N: エクササイズの種類数
    # M: トレーニングを行いたい日数
    # K: 1回のトレーニングで減る回数
    n = int(input_data[0])
    m = int(input_data[1])
    k = int(input_data[2])
    
    # 2行目の A_1, A_2, ..., A_N を順番に処理します
    # 各エクササイズ i について、最大で floor(A_i / K) 回のトレーニングが可能です
    total_possible_sessions = 0
    for i in range(n):
        # A_i は input_data のインデックス 3 以降に格納されています
        a_i = int(input_data[3 + i])
        total_possible_sessions += a_i // k
        
    # 合計の可能回数が M 回以上であれば、M 日間トレーニングを続けることができます
    if total_possible_sessions >= m:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。