概要

長さ \(L\) のロープを最大 \(K\) 回切って \(K+1\) 本以下のピースに分け、各生徒に必要な長さ以上のロープを1本ずつ配るとき、工作に参加できる生徒数を最大化する問題です。

考察

重要な気づき

1. ロープは最大 \(K+1\) 本まで：\(K\) 回切ると最大 \(K+1\) 本のピースができます。つまり、配れる生徒は最大 \(K+1\) 人です。

2. 貪欲法が有効：できるだけ多くの生徒に配りたいなら、必要なロープが短い生徒を優先すべきです。

なぜ短い方から配るのか？

具体例で考えてみましょう。

• ロープの長さ \(L = 10\)、最大カット回数 \(K = 2\)（最大3本）
• 生徒の必要な長さ：\(A = [2, 3, 6]\)

短い方から配る場合： - 生徒1に長さ2を配る → 残り8 - 生徒2に長さ3を配る → 残り5 - 生徒3は長さ6必要だが残り5しかない → 配れない - 結果：2人に配れる

長い方から配る場合： - 生徒3に長さ6を配る → 残り4 - 生徒2は長さ3必要 → 残り1 - 生徒1は長さ2必要だが残り1しかない → 配れない - 結果：2人に配れる

この例では同じですが、\(A = [1, 1, 9]\)、\(L = 10\) の場合： - 短い方から：1 + 1 + 9 = 11 > 10 なので2人 - 長い方から：9 + 1 = 10 なので2人

実は同じになりますが、短い方から取ることで「より多くの生徒を検討できる」という利点があります。

アルゴリズムの正当性

必要な長さが短い生徒から順に配ることで、同じロープ消費量でより多くの生徒に配れます。これは貪欲法の典型的なパターンです。

アルゴリズム

1. 配列 \(A\) を昇順にソートする
2. 必要なロープが短い生徒から順に、ロープを割り当てていく
3. 以下の条件を満たす限り、生徒にロープを配り続ける：
   • これまでに配った生徒数が \(K+1\) 未満
   • これまでに配ったロープの長さの合計 + 今の生徒に必要な長さ \(\leq L\)
4. 配れた生徒数を出力する

total_length = 0, count = 0
for each student i (sorted by A[i]):
    if count >= K+1: break
    if total_length + A[i] <= L:
        total_length += A[i]
        count += 1
    else:
        break
return count

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • ループで \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) の保存に \(O(N)\)

実装のポイント

1. ソートの方向：昇順ソートして、必要量が少ない生徒から処理することが重要です。

2. ループの終了条件：以下の2つの条件のどちらかを満たしたら終了します：

   • 配った人数が \(K+1\) に達した（これ以上ピースを作れない）
   • 残りのロープでは次の生徒の要求を満たせない

3. 早期終了の最適化：ソート済みなので、一度「長さが足りない」となったら、それ以降の生徒も必ず足りません。そのため break で即座にループを抜けられます。

   ソースコード

def solve():
    N, L, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sort A in ascending order to prioritize students who need less rope
    A.sort()
    
    # We can make at most K cuts, resulting in at most K+1 pieces
    # We want to maximize the number of students who can participate
    
    # Greedy approach: Give rope to students who need the least amount first
    # This way we can maximize the number of students
    
    # We can give rope to at most min(K+1, N) students
    max_pieces = K + 1
    
    # Try to give rope to as many students as possible
    # Starting from students who need the least rope
    
    total_length = 0
    count = 0
    
    for i in range(N):
        if count >= max_pieces:
            break
        if total_length + A[i] <= L:
            total_length += A[i]
            count += 1
        else:
            break
    
    print(count)

solve()

---

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