概要

各風船を割るのに必要な投擲回数を最小化し、その回数が少ない風船から順に割っていくことで、\(K\) 回以内に割れる風船数の最大値を求めます。

考察

重要な気づき 1：使うべきダーツは「攻撃力最大の1本」だけでよい

1 回の投擲で選べるダーツは自由で、何度でも使えます。
風船を割るには耐久値を \(0\) 以下にすればよいので、同じ風船を割るまでに必要な投擲回数を減らしたいです。

攻撃力が最大のダーツを \(p_{\max}=\max(P)\) とすると、耐久値 \(H\) の風船を割るのに必要な最小投擲回数は - 最大ダーツだけを使えば \(\left\lceil \dfrac{H}{p_{\max}} \right\rceil\) - それ以外のダーツを混ぜても、1 回あたりの減少量が小さくなる可能性があるため、投擲回数がこれより少なくなることはありません

したがって「各風船を割る最短手数」は常に最大攻撃力ダーツだけで達成でき、最適解でも最大ダーツ以外を使う必要がありません。

重要な気づき 2：「各風船を割るコスト」が分かれば、あとは小さい順に選べばよい

各風船を割るのに必要な投擲回数（コスト）を \(c_i\) とすると、目的は

• 合計コスト \(\sum c_i \le K\) を満たしつつ
• 選んだ風船の個数を最大化

です。各風船の価値はすべて「1 個割れる」という同一価値なので、コストが小さいものから順に割るのが最適です（より多くの個数を詰め込めるため）。

素朴解がダメな理由

• \(K\) は最大 \(10^{18}\) なので、1 投ずつシミュレーションする方法は不可能です。
• 風船ごとの最適なダーツ選択を状態として持つような DP も、\(N, M\) が最大 \(2\times 10^5\) で現実的ではありません。

「最大ダーツだけに絞る」→「風船ごとの必要回数を計算」→「小さい順に貪欲」という形に落とし込むのがポイントです。

具体例

\(P = [3, 5]\) なら \(p_{\max}=5\)。
風船耐久 \(H=[4,9,10]\) のとき必要回数は - \(4\): \(\lceil 4/5\rceil=1\) - \(9\): \(\lceil 9/5\rceil=2\) - \(10\): \(\lceil 10/5\rceil=2\)

\(K=3\) なら、\(1,2,2\) を小さい順に足していき \(1+2=3\) までなので、最大で 2 個割れます。

アルゴリズム

1. ダーツ攻撃力の最大値 \(p_{\max}=\max(P)\) を求める。
2. 各風船 \(i\) について、最大ダーツだけで割る最小投擲回数（コスト）を計算する。
   [ c_i = \left\lceil \frac{Hi}{p{\max}} \right\rceil ] 整数演算では [ c_i = \frac{Hi + p{\max} - 1}{p_{\max}} \text{ の切り捨て} ] を使う。
3. コスト配列 \(c\) を昇順ソートする。
4. 小さい順に足していき、累積和が \(K\) を超えない限り数える（貪欲）。
5. 数えられた個数を出力する。

計算量

• 時間計算量: \(O(N \log N + M)\)（最大値計算が \(O(M)\)、コストのソートが \(O(N\log N)\)）
• 空間計算量: \(O(N)\)（コスト配列を保持）

実装のポイント

• \(\left\lceil \dfrac{H}{p} \right\rceil\) は (H + p - 1) // p で計算する（浮動小数点を使わない）。

• \(H_i, P_j, K\) は最大 \(10^{18}\) なので 64bit 整数相当が必要（Python の int なら安全）。

• ソート後は累積和が \(K\) を超えた時点で打ち切ると無駄がありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))
    P = list(map(int, input().split()))
    pmax = max(P)

    costs = [(h + pmax - 1) // pmax for h in H]
    costs.sort()

    s = 0
    ans = 0
    for c in costs:
        if s + c > K:
            break
        s += c
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。