概要

長さ \(L\) の1本のロープを最大 \(K\) 回まで切り分け、各生徒 \(i\) が必要とする最小の長さ \(A_i\) を満たすように配ることで、最大何人の生徒が工作に参加できるかを求める問題です。

考察

この問題を解くための重要なポイントは以下の2点です。

1. 欲張り法（Greedy）の適用 できるだけ多くの人数にロープを配るためには、「必要とするロープの長さ \(A_i\) が短い生徒」から優先的に配るのが最適です。長いロープを必要とする生徒に配るよりも、短いロープで満足してくれる生徒に配るほうが、残りのロープをより多くの人数で分け合えるからです。

2. 2つの制約の考慮 生徒にロープを配る際、以下の2つの限界を同時に満たす必要があります。

   • カット回数の限界: ロープを \(K\) 回切って作れるピースの数は最大 \(K+1\) 本です。そのため、配れる生徒の人数は最大でも \(\min(N, K+1)\) 人となります。
   • 総長の限界: 配るロープの長さの合計は、元のロープの長さ \(L\) を超えてはいけません。

したがって、生徒が必要な長さ \(A_i\) を昇順（小さい順）に並べ、先頭から順番に「合計の長さが \(L\) を超えないか」かつ「人数が \(K+1\) を超えないか」を確認していくことで、答えを導き出すことができます。

アルゴリズム

1. 各生徒が必要な長さのリスト \(A\) を昇順にソートします。
2. 工作に参加できる人数の上限を limit = min(N, K + 1) とします。
3. ソートされた \(A\) の先頭から順に limit 人分まで確認します。
4. 現在まで選んだ生徒の必要とする長さの合計が \(L\) 以下であれば、その生徒をカウントに加えます。
5. 合計が \(L\) を超えた時点、または limit 人に達した時点で処理を終了し、カウントした人数を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 入力の読み込みに \(O(N)\)、リスト \(A\) のソートに \(O(N \log N)\)、その後の線形走査に \(O(N)\) かかります。全体としてソートの計算量が支配的になります。
• 空間計算量: \(O(N)\)
  • \(N\) 人分の生徒の要求量 \(A_i\) をリストに保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大量の入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を用いて一括で入力を取得し、高速化を図っています。

• カット回数とピース数: 「カット回数 \(K\)」に対して「ピースの数 \(K+1\)」になるという点に注意が必要です。たとえロープの長さ \(L\) が十分にあっても、\(K+1\) 人より多くの生徒に配ることはできません。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを高速に処理できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 入力の最初の3つの値（N, L, K）を取得します。
    n = int(input_data[0])
    l = int(input_data[1])
    k = int(input_data[2])
    
    # 各生徒が必要とする最小のロープの長さ A_i をリストとして取得します。
    a = list(map(int, input_data[3:]))
    
    # 少ない長さを必要とする生徒から優先的に配ることで、
    # 工作に参加できる人数を最大化できるため、A_i を昇順にソートします。
    a.sort()
    
    ans = 0
    current_total_length = 0
    
    # ロープを最大 K 回切ることができるため、作れるピースの最大数は K + 1 です。
    # したがって、工作に参加できる生徒の最大人数は、生徒数 N と K + 1 の小さい方になります。
    max_satisfiable_students = min(n, k + 1)
    
    # 条件を満たす生徒の人数を数えます。
    for i in range(max_satisfiable_students):
        # 現在注目している生徒にロープを配ったときの合計の長さが、
        # 持っているロープの総長 L 以下であれば、その生徒に配ることができます。
        if current_total_length + a[i] <= l:
            current_total_length += a[i]
            ans += 1
        else:
            # 合計が L を超える場合は、これ以上生徒に配ることはできません。
            break
            
    # 最大人数を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

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