考察
持っていくお守りを直接選ぶより、置いていくお守りの被害を小さい順に足すと、何個まで置いていけるかが分かる。討伐数を一体増やすたびに変わるのは一種類の被害だけなので、この選択の境界を二集合で更新する。
討伐数を固定すると、小さい被害から選べる
お守りの個数ごとに選び方を全探索すると、種類数に対して指数時間かかる。そこで要求を逆にして、先頭の 体を倒すのに必要なお守りの最小個数を とする。最後に、各所持数 に対して となる最大の を求めればよい。
先頭の 体に含まれるタイプ の攻撃力の合計を とする。お守り を置いていくと、この合計だけ被害を受ける。攻撃力は正なので、先頭の 体を倒せる条件は、置いていく種類の被害の総和が 未満であることだ。最後までの合計が 未満なら途中でも生きている。一方、被害が に達した時点で力尽き、そのモンスターは倒せない。
置いていく個数を固定すると、 が小さい種類から選ぶほど総被害は小さい。したがって、全種類を小さい順に並べ、累積和が 未満になる最長の接頭辞を選べば、置いていける個数が最大になる。ここで接頭辞とは、並びの先頭から何個かを取った部分を指す。例えば なら、最初の二種類は合計3で置いていけるが、三種類では合計6となる。必要なお守りは残りの一個である。
この並べ直しを各 で行うと全体で 時間かかる。ところが、先頭の範囲を一体伸ばしても、増えるのは だけだ。並び全体を作り直す代わりに、選ぶ側と選ばない側の境界だけを修復できないかを考える。
小さい側の接頭辞を、最大性まで含めて保つ
置いていく種類の集合を 、持っていく種類の集合を とする。各種類はどちらか一方にだけ置く。両集合を平衡二分木などの順序付き集合で保持し、種類 のキーには を使う。まず被害で比較し、同値なら種類番号で比較すれば、同じ被害の種類も区別できる。
の被害の総和を とし、処理が終わるたびに次の三条件を保つ。
- 順序:両集合が空でないなら の最大キーは の最小キー以下。つまり は全キーの小さい側の接頭辞である。
- 生存:。
- 最大性: が空、または 。ここで は の最小キーの種類であり、次の一種類は追加できない。
順序と生存だけでは、取り足りない可能性がある。先ほどの で としても、その二条件は満たすが、種類2をまだ追加できる。三つ目の条件まであって初めて が最大といえる。必要所持数は である。
初期状態は 、全種類の とする。全種類を に入れ、 は空、 とすれば三条件を満たす。未登場の種類も省かない。例えば最初にタイプ1だけが現れたときも、タイプ2と3のキー は別々に残り、どちらのお守りも被害なしで置いていける。
更新は「同じ側へ戻す、順序を直す、和を直す」
モンスター を追加するときは、 として次の順で操作する。以下で集合間を移すたびに、 も移した種類の被害だけ増減する。
- 種類 がいた側を覚え、旧キー をその集合から削除する。 にいたなら から旧 を引く。
- とし、新キーを元と同じ側へ挿入する。 へ戻したなら に新 を足す。
- 両集合が空でなく、 の最大キーが の最小キーより大きければ、その二種類を交換する。 から出る種類を 、入る種類を として、 とする。この交換は一回で順序を回復する。
- なら、 の最大キーの種類を一つだけ へ移し、 からその被害を引く。この移動は一回で生存と最大性を回復する。
- を記録する。
例えば では、 である。ここでタイプ1の被害が3増えると、同じ側へ戻した直後は の被害が4と2になり、 となる。まず種類1と3を交換すると、 は小さい側の二種類になるが、 で生存条件を満たさない。そこで種類3を へ移す。最終的に となり、次に小さい被害3を足すとちょうど5なので追加できない。必要所持数は1から2へ増える。
この規則では、和を直した後に追加するループは要らない。被害は一種類だけ増えるので、置いていける最大個数は増えず、減っても一個だけである。順序の修復で交換が一回、和の修復で移動が一回で足りる理由を「正当性」で示す。
必要個数の列を、全所持数の答えへ戻す
被害が増えるほど必要所持数 は減らない。各 について、答えは
となる。必要数より多くお守りを持っても被害は増えないので、「ちょうど 個」という条件にも対応する。
を0から増やしながら、討伐数のポインタ を0から進める。 かつ の間だけ を増やし、その時点の を とする。ポインタは戻らず、全 を合計 時間で処理できる。
小例として 、モンスターの が順に なら、上の更新例を含み、 となる。所持数0では二体、1では三体、2以上では全四体を倒せるので、 である。
典型の発動条件
動的 k-smallest sum の二集合管理
一点更新される非負の重みから、和が上限未満になる最大個数を選ぶときに使う。採用側を小さい順の接頭辞とし、境界の順序・総和・次を追加できない条件を別々に保つ。固定個数の和を求める問題と違い、採用個数そのものの最大性も必要になる。
更新が一個でも、修復が定数回とは限らない。本問では「一種類の増加」と「各種類が個数1に寄与すること」から、最適個数の変化を一個以内に抑えられる。減少更新や重み付きの個数へ、その結論をそのまま移さない。
閾値列の逆引き
長さごとに必要な最小資源を求める方が簡単で、必要資源が長さに対して非減少なら、資源量ごとの最大の長さへ逆引きできる。資源量の昇順に一つのポインタを進めれば、各要素に独立に二分探索するよりもまとめて処理できる。
問題固有の要素
お守りは同じタイプの攻撃をすべて防ぐので、討伐数を固定すれば、各タイプの影響を一つの被害合計へまとめられる。さらに「持つ側」から「置いていく側」へ反転すると、非負の被害を上限未満に詰める個数最大化になる。防げる被害を直接最大化する前に、補集合で制約が単純になるかを見るのが着眼点である。
正当性
ある個数のお守りを置いていくとき、キーが大きい種類を選び、それより小さいキーの種類を選んでいなければ、その二種類を交換しても総被害は増えない。交換を繰り返すと小さい側の接頭辞になるため、各個数における総被害の最小値はその接頭辞の和である。よって、順序・生存・最大性の三条件を満たす は、置いていける個数を最大にする。
次に、一種類の正の増加に対する更新を確認する。更新前の最大個数を 、更新後を とする。どの選択も被害が減らないので である。一方、変更した種類が旧 にあれば、それを外した残りの 種類の被害は変わらず、総和も 未満である。旧 にあれば旧 自体が引き続き選べる。したがって では であり、 では となる。
手順2の直後も である。旧 のキーを増やした場合は、境界の順序は崩れない。旧 のキーを増やした場合、順序を崩せるのはその一キーだけであり、崩れたならそれが の最大キーである。これを旧 の最小キーと交換すると、残りの旧 の全キーは交換で入るキー以下であり、交換で出るキーも残る の全キーも、そのキー以上になる。従って手順3の交換一回で、 は新しい並びの小さい 個になる。
その和が 未満なら 個を選べ、 と合わせて個数は最大である。和が 以上なら、どの 個も選べないので である。手順4で最大キーを一つ外すと、小さい 個になり、その和は選べる 個の中で最小なので 未満になる。外した種類を足し直すと直前の和に戻って 以上となるため、最大性も満たす。 なら なのでこの移動は起きない。このように、交換・移動はそれぞれ高々一回で三条件を回復する。
初期状態は三条件を満たし、各更新もこれを回復するため、得られる は各討伐数の必要最小個数である。被害は非負なので先頭の 体までの合計が生存条件を満たせば途中でも生存でき、余分なお守りを持っても被害は増えない。従って、 を満たす最大の を求める逆引きは、所持数がちょうど のときの答えを返す。
実装上の注意
- 生存判定は とする。 でも死亡し、そのモンスターは倒せない。特に なら、被害0の種類だけが に入る。
- 旧キーを削除してから を変更し、元と同じ集合へ新キーを挿入する。種類ごとの所属を配列で記録するか、旧キーを検索して判定する。交換や移動時には所属と も更新する。
- をキーにすれば同じ被害の種類も消えない。例えば被害がともに2の種類1と2は として保持し、種類1の更新で種類2まで削除しない。
- 最大・最小キーの参照前に空でないことを確認する。全種類を置いていけるときは が空、一種類も置いていけないときは が空になる。
- と は符号付き64 bit整数で持つ。総被害は最大 であり、和の修復前には になることもある。
- を含めて保存し、逆引きでは を先に確かめてから を参照する。 なら全攻撃を防げるので、必ず となる。
復習の核
- 資源量ごとの最大到達点が欲しいときは、到達点ごとの必要最小資源を求める向きも考える。
- 小さい側の接頭辞であることと、上限まで最大個数を取っていることは別条件。「次の一個を足せない」まで確かめる。
- 一点更新を見たら、最適な個数と境界の要素がそれぞれどれだけ変わるかを調べる。修復回数は、その変化幅から証明する。
計算量と制約
時間
初期の キーを一つずつ挿入すると 。各モンスターの処理では旧キーの削除・新キーの挿入に加え、交換と移動がそれぞれ高々一回なので 時間かかる。必要数の列から全所持数の答えを求める処理は 。全体で 時間である。 より、 とも書ける。
空間
全種類の被害・所属と二集合に 、必要所持数の列に 、答えの配列に を使い、全体で 。
制約との対応
、、。全タイプが入力全体には現れるが、途中の討伐範囲には未登場でもよい。正の攻撃力により被害が単調に増え、最大個数の変化を一個以内に抑えられるため、各回の全種類の並べ直しを避けられる。
出典
公式問題・個別公式解説を2026-10-23に再照合した。三条件を回復する具体的な更新規則と、交換・移動がそれぞれ高々一回となる論証は、本教材で補足した。