概要

\(N\) 個の風船を最大何個割れるかを求める問題です。最も攻撃力の高いダーツだけを使い、耐久値の低い風船から貪欲に割っていくのが最適です。

考察

重要な気づき①：最強のダーツだけ使えばよい

\(M\) 本のダーツの中で最も攻撃力が高いもの（\(P_{\max}\) とする）だけを使うのが最適です。なぜなら、どの風船を割る場合でも、攻撃力が最大のダーツを繰り返し投げるのが最も少ない投擲回数で割れるからです。攻撃力が低いダーツを使う理由はありません。

重要な気づき②：各風船を割るのに必要な投擲回数

風船 \(i\) の耐久値が \(H_i\) で、毎回 \(P_{\max}\) ずつ減らすとき、割るのに必要な投擲回数は：

\[\left\lceil \frac{H_i}{P_{\max}} \right\rceil\]

です。例えば \(H_i = 10\), \(P_{\max} = 3\) なら \(\lceil 10/3 \rceil = 4\) 回投げれば耐久値が \(10 - 3 \times 4 = -2 \leq 0\) となり割れます。

重要な気づき③：コストが小さい風船から割る（貪欲法）

\(K\) 回以下の投擲で最大何個割れるかを最大化したいので、必要投擲回数（コスト）が小さい風船から優先的に割るのが最適です。コストの小さい順にソートし、累積和が \(K\) を超えない限り割り続ければよいです。

素朴なアプローチとの比較

全風船×全ダーツの組み合わせを考えると計算量が爆発しますが、「最強のダーツだけ使えばよい」という観察により、問題が大幅に単純化されます。

アルゴリズム

1. ダーツの最大攻撃力 \(P_{\max} = \max(P_1, P_2, \ldots, P_M)\) を求める。
2. 各風船 \(i\) について、割るのに必要な投擲回数 \(c_i = \lceil H_i / P_{\max} \rceil\) を計算する。
3. \(c_i\) を昇順にソートする。
4. 小さい方から順に \(c_i\) を累積加算し、累積和が \(K\) 以下である限りカウントを増やす。
5. そのカウントが答え。

具体例: \(N=3\), \(M=2\), \(K=5\), \(H=[7, 3, 10]\), \(P=[3, 4]\) の場合

• \(P_{\max} = 4\)
• 各風船のコスト: \(\lceil 7/4 \rceil = 2\), \(\lceil 3/4 \rceil = 1\), \(\lceil 10/4 \rceil = 3\)
• ソート後: \([1, 2, 3]\)
• 累積和: \(1, 3, 6\)
• \(K=5\) なので、\(1+2=3 \leq 5\) ✓, \(1+2+3=6 > 5\) ✗
• 答え: 2

計算量

• 時間計算量: \(O(N \log N + M)\)
  • \(M\) 個のダーツから最大値を求める: \(O(M)\)
  • \(N\) 個のコスト計算: \(O(N)\)
  • ソート: \(O(N \log N)\)
  • 累積和の走査: \(O(N)\)
• 空間計算量: \(O(N + M)\)（入力とコスト配列の格納）

実装のポイント

• 天井除算（切り上げ割り算）は (H + P_max - 1) // P_max で整数演算のみで計算できます。Python の math.ceil を使う場合、大きな整数で浮動小数点の誤差が生じる可能性があるため、整数演算が安全です。

• \(K\) や \(H_i\) が最大 \(10^{18}\) と非常に大きいため、オーバーフローに注意が必要です（Python では整数の大きさに制限がないため問題ありません）。

• 累積和が \(K\) を超えた時点でループを打ち切ることで、無駄な計算を省けます。

  ソースコード

import sys
from math import ceil

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    P = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    # Use the strongest dart
    max_P = max(P)
    
    # For each balloon, compute minimum number of throws to break it
    # ceil(H_i / max_P)
    # To break a balloon with durability H using dart with power max_P:
    # need ceil(H / max_P) throws
    
    costs = []
    for h in H:
        costs.append((h + max_P - 1) // max_P)
    
    # Sort costs in ascending order - break cheapest balloons first
    costs.sort()
    
    # Use prefix sums to find maximum number of balloons we can break with K throws
    # Binary search or just prefix sum scan
    
    count = 0
    total = 0
    for c in costs:
        total += c
        if total <= K:
            count += 1
        else:
            break
    
    print(count)

solve()

---

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