概要

複数あるダーツの中から最適なものを使い、限られた投擲（とうてき）回数内でできるだけ多くの風船を割る問題です。

考察

この問題を解くための重要な気づきは以下の2点です。

1. どのダーツを使うべきか？ 各ダーツは何度でも使うことができます。1回の投擲で減らせる耐久値は大きいほど良いため、攻撃力が最大のダーツだけを使い続けるのが常に最適です。攻撃力が低いダーツを選ぶメリットは一切ありません。

2. どの風船から狙うべきか？ 割れる風船の数を最大化したいので、少ない投擲回数で割れる風船から優先して狙うのが最適です（貪欲法）。

もし、ダーツを投げるたびに風船の耐久値を \(1\) 回ずつ減らすような愚直なシミュレーションを行うと、投擲回数 \(K\) は最大 \(10^{18}\) と非常に大きいため、制限時間超過（TLE）になってしまいます。 そのため、割り算を使って「各風船を割るために必要な投擲回数」をまとめて計算する必要があります。

最大の攻撃力を持つダーツを使い続けた場合、耐久値 \(H_i\) の風船を割るために必要な回数は、以下のように計算できます。 $\( \lceil H_i \div (\text{最大の攻撃力}) \rceil \)\( （\)\lceil x \rceil\( は \)x$ 以上の最小の整数、つまり切り上げを表します）

あとは、この必要な回数が少ない風船から順に、合計回数が \(K\) を超えない範囲で割っていけば正解を導くことができます。

アルゴリズム

1. ダーツの攻撃力 \(P_1, P_2, \ldots, P_M\) の中から、最大値 max_P を見つけます。
2. 各風船について、割るために必要な投擲回数 \(\lceil H_i / \text{max\_P} \rceil\) を計算し、リストに保存します。
3. 計算した「必要な投擲回数」のリストを昇順（小さい順）にソートします。
4. リストを前から順に確認し、残り投擲回数 \(K\) から必要な回数を引いていきます。
5. \(K\) が足りなくなったら（またはすべての風船が割れたら）終了し、割れた風船の数を出力します。

計算量

• 時間計算量: \(O(N \log N + M)\)
  • ダーツの最大攻撃力を探すのに \(O(M)\)
  • 各風船の必要回数を計算するのに \(O(N)\)
  • 必要回数のソートに \(O(N \log N)\)
  • 風船を割る処理に \(O(N)\)
  • 全体として \(O(N \log N + M)\) となり、制約下で十分に高速です。
• 空間計算量: \(O(N + M)\)
  • 入力データの保持や、各風船の必要回数を保存するリストにメモリを使用します。

実装のポイント

風船を割るのに必要な回数を求める際、割り算の「切り上げ」を行う必要があります。 Pythonなどで math.ceil(H_i / max_P) のように浮動小数点数（小数）を使って計算すると、数値が非常に大きい場合に精度誤差が生じて不正解（WA）になる危険性があります。

これを防ぐため、すべて整数で計算するテクニックを使います。 整数 \(A\) を \(B\) で割った切り上げは、以下のように書くことができます。 $\( (A + B - 1) \mathbin{//} B \)$ （// は切り捨て除算）

例えば、風船の耐久値 \(A = 7\)、最大の攻撃力 \(B = 3\) の場合、必要な回数は \(3\) 回です。 この式に当てはめると、\((7 + 3 - 1) \mathbin{//} 3 = 9 \mathbin{//} 3 = 3\) となり、正しく計算できていることが分かります。競技プログラミングで頻出のテクニックなので覚えておきましょう。

ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    H = [int(x) for x in input_data[3:3+N]]
    P = [int(x) for x in input_data[3+N:3+N+M]]
    
    max_P = max(P)
    
    costs = [(h + max_P - 1) // max_P for h in H]
    costs.sort()
    
    ans = 0
    for c in costs:
        if K >= c:
            K -= c
            ans += 1
        else:
            break
            
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。