本問題を解くには、全ての \(i = 0, 1, 2, \ldots, N\) に対する、モンスターを \(i\) 体以上倒すために持っていく必要があるお守りの個数 \(L_i\) が十分高速に求められれば良いです。 なぜなら、\(L = (L_0, L_1, \ldots, L_N)\) が与えられたとき、\(K = i\) における問題の答えは \(L_j \leq i\) を満たす最大の \(j\) であり、これは \(L\) 上での二分探索や尺取法によって十分高速に求められるからです。

\(i\) を固定し、\(L_i\)を 求めることを考えます。 ここでは \(L_i\) の代わりに \(M-L_i\) 、つまり、モンスターを \(i\) 体倒す上で持っていかずに置いていくことが許されるお守りの個数の上限を求めます。

各タイプ \(j = 1, 2, \ldots, M\) に対して、\(C_j\) をモンスター \(1\) からモンスター \(i\) までのうちタイプが \(j\) であるモンスターの攻撃力の総和とします。 このとき、お守り \(j\) を置いていく選択をすることは、モンスター \(i\) を倒すまでにタイプ \(j\) のモンスターから合計 \(C_j\) のダメージを受けることを許容することになります。 モンスター \(i\) を倒すまでに許容できるダメージの合計は \(H-1\) であり、冒険に置いていくお守りとしては \(C_j\) が小さいお守り \(j\) から優先的に選ぶのが最適ですので、\(M - L_i\) は、

\(M\) 個のお守りを \(C_j\) が小さいものから貪欲に、選んだお守りの \(C_j\) の総和が \(H\) 未満である限り選ぶときの、選ぶ個数

です。

\(1\) つの \(i\) での \(L_i\) の求め方がわかったので、最後に、すべての \(i\) で \(L_i\) を求めることを考えます。 上で述べた方法で \(L_i\) を求めることを全ての \(i\) で愚直に行うと計算量が過大になるため工夫が必要です。 ここで、

\(i\) を \(1\) 増加させても \(C_1, C_2, \ldots, C_M\) のうち値が変化するのは \(C_{B_{i+1}}\) の \(1\) 個だけであり、それゆえ、持っていくお守りの集合 \(S\) と置いていくお守りの集合 \(T\) も、\(i\) が \(1\) 増加したことによって高々定数個の要素しか変化しない

ことに注目します。 このことを用いると、\(S, T\) それぞれを要素の追加・削除・最大/最小要素の取得が対数時間で可能な平衡二分木などのデータ構造で保持することで、\(i\) を \(1\) 増やした際には、わずかな差分のみの更新によって古い \(i\) に関する \(C, S, T\) から新しい \(i\) に対する \(C, S, T\) を \(O(\log M)\) 時間で得ることができます。 これによって、\(i = 0, 1, 2, \ldots, N\) について \(i\) を \(1\) ずつ増やしながら順次 \(L_i\) を十分高速に求めることができ、本問題を全体で \(O(M + N\log M)\) 時間で解くことができます。