概要

風船割りゲームにおいて、限られた回数のダーツ投擲で割れる風船の最大数を求める問題です。

考察

この問題では、\(K\) 回以内の投擲でできるだけ多くの風船を割るのが目的です。素朴な方法として、全ての風船に対して必要な最小投擲回数を一つずつ計算し、それを少ない順に取っていく方法が考えられます。

しかし、風船とダーツの数が最大で \(2 \times 10^5\) あり、さらに \(K\) が非常に大きい（最大 \(10^{18}\)）ため、全組み合わせを試すことは不可能です。そこで重要なのは「どの風船を割るか」ではなく、「どのように効率的に多くの風船を割るか」という視点に立ち直ることです。

ここで重要な観察があります：

各風船を割るために必要な最小の投擲回数は、最も攻撃力の高いダーツ（最大攻撃力）を使うのが最適です。

なぜなら、同じ風船を複数回狙うことができ、どのダーツを使ってもよいので、最も効率の良い（＝攻撃力最大の）ダーツを使えば、最も少ない回数で風船を割ることができるからです。

したがって、各風船 \(i\) について、その耐久値 \(H_i\) を最大攻撃力 \(max\_P\) で割った値（切り上げ）が、その風船を割るのに必要な最小投擲回数になります： $\( \text{min\_darts}_i = \left\lceil \frac{H_i}{max\_P} \right\rceil \)$

この値をすべての風船について求め、小さい順にソートすることで、「コストの低い順に貪欲に取る」ことが可能です。つまり、合計が \(K\) を超えない範囲で、必要な投擲回数が少ない風船から順番に割っていけば、最大数を得られます。

アルゴリズム

1. 最も攻撃力の高いダーツの攻撃力を \(max\_P\) とする。
2. 各風船 \(i\) について、\(\left\lceil \frac{H_i}{max\_P} \right\rceil\) を計算し、リスト min_darts_needed に格納する。
3. min_darts_needed を昇順にソートする。
4. ソートされたリストの先頭から、合計が \(K\) を超えないように風船を選び、選べた数をカウントしていく。
5. カウントした数が答え。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)

実装のポイント

• 切り上げ除算 \(\left\lceil a / b \right\rceil\) は (a + b - 1) // b で実現可能（整数同士の場合）。

• 最大攻撃力を持つダーツは1回選べば十分であり、毎回探索する必要はない。

• 風船の情報をソートする前に、必要な最小投擲回数を前処理しておくこと。

  ソースコード

import sys
import heapq
from bisect import bisect_left

def input():
    return sys.stdin.readline().rstrip()

def main():
    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # 最大攻撃力で割れる風船の上限を求める
    max_P = max(P)
    
    # 各風船を割るのに必要な最小投擲回数を求める
    # 各H[i]について、ceil(H[i] / max_P) を計算
    min_darts_needed = []
    for h in H:
        if h <= max_P:
            min_darts_needed.append(1)
        else:
            # ceil(h / max_P)
            min_darts_needed.append((h + max_P - 1) // max_P)
    
    # 投擲回数の最小値でソートして、貪欲に割れる風船を選ぶ
    min_darts_needed.sort()
    
    count = 0
    total = 0
    for d in min_darts_needed:
        if total + d <= K:
            total += d
            count += 1
        else:
            break
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。