ABC 314 G — Amulets

考察

持っていくお守りを直接選ぶより、置いていくお守りの被害を小さい順に足すと、何個まで置いていけるかが分かる。討伐数を一体増やすたびに変わるのは一種類の被害だけなので、この選択の境界を二集合で更新する。

討伐数を固定すると、小さい被害から選べる

お守りの個数ごとに選び方を全探索すると、種類数に対して指数時間かかる。そこで要求を逆にして、先頭の ii 体を倒すのに必要なお守りの最小個数を LiL_i とする。最後に、各所持数 KK に対して Li≤KL_i\leq K となる最大の ii を求めればよい。

先頭の ii 体に含まれるタイプ jj の攻撃力の合計を CjC_j とする。お守り jj を置いていくと、この合計だけ被害を受ける。攻撃力は正なので、先頭の ii 体を倒せる条件は、置いていく種類の被害の総和が HH 未満であることだ。最後までの合計が HH 未満なら途中でも生きている。一方、被害が HH に達した時点で力尽き、そのモンスターは倒せない。

置いていく個数を固定すると、CjC_j が小さい種類から選ぶほど総被害は小さい。したがって、全種類を小さい順に並べ、累積和が HH 未満になる最長の接頭辞を選べば、置いていける個数が最大になる。ここで接頭辞とは、並びの先頭から何個かを取った部分を指す。例えば C=(1,2,3), H=5C=(1,2,3),\ H=5 なら、最初の二種類は合計3で置いていけるが、三種類では合計6となる。必要なお守りは残りの一個である。

この並べ直しを各 ii で行うと全体で O(NMlog⁡M)O(NM\log M) 時間かかる。ところが、先頭の範囲を一体伸ばしても、増えるのは CBiC_{B_i} だけだ。並び全体を作り直す代わりに、選ぶ側と選ばない側の境界だけを修復できないかを考える。

小さい側の接頭辞を、最大性まで含めて保つ

置いていく種類の集合を TT、持っていく種類の集合を SS とする。各種類はどちらか一方にだけ置く。両集合を平衡二分木などの順序付き集合で保持し、種類 jj のキーには (Cj,j)(C_j,j) を使う。まず被害で比較し、同値なら種類番号で比較すれば、同じ被害の種類も区別できる。

TT の被害の総和を W=∑j∈TCjW=\sum_{j\in T}C_j とし、処理が終わるたびに次の三条件を保つ。

  1. 順序:両集合が空でないなら TT の最大キーは SS の最小キー以下。つまり TT は全キーの小さい側の接頭辞である。
  2. 生存:W<HW<H。
  3. 最大性:SS が空、または W+Cs≥HW+C_s\geq H。ここで ss は SS の最小キーの種類であり、次の一種類は追加できない。

順序と生存だけでは、取り足りない可能性がある。先ほどの C=(1,2,3), H=5C=(1,2,3),\ H=5 で T={1}, S={2,3}T=\{1\},\ S=\{2,3\} としても、その二条件は満たすが、種類2をまだ追加できる。三つ目の条件まであって初めて ∣T∣|T| が最大といえる。必要所持数は Li=M−∣T∣L_i=M-|T| である。

初期状態は i=0i=0、全種類の Cj=0C_j=0 とする。全種類を TT に入れ、SS は空、W=0, L0=0W=0,\ L_0=0 とすれば三条件を満たす。未登場の種類も省かない。例えば最初にタイプ1だけが現れたときも、タイプ2と3のキー (0,2),(0,3)(0,2),(0,3) は別々に残り、どちらのお守りも被害なしで置いていける。

更新は「同じ側へ戻す、順序を直す、和を直す」

モンスター ii を追加するときは、b=Bib=B_i として次の順で操作する。以下で集合間を移すたびに、WW も移した種類の被害だけ増減する。

  1. 種類 bb がいた側を覚え、旧キー (Cb,b)(C_b,b) をその集合から削除する。TT にいたなら WW から旧 CbC_b を引く。
  2. Cb←Cb+AiC_b\leftarrow C_b+A_i とし、新キーを元と同じ側へ挿入する。TT へ戻したなら WW に新 CbC_b を足す。
  3. 両集合が空でなく、TT の最大キーが SS の最小キーより大きければ、その二種類を交換する。TT から出る種類を tt、入る種類を ss として、W←W−Ct+CsW\leftarrow W-C_t+C_s とする。この交換は一回で順序を回復する。
  4. W≥HW\geq H なら、TT の最大キーの種類を一つだけ SS へ移し、WW からその被害を引く。この移動は一回で生存と最大性を回復する。
  5. Li=M−∣T∣L_i=M-|T| を記録する。

例えば C=(1,2,3), H=5C=(1,2,3),\ H=5 では、T={1,2}, S={3}, W=3T=\{1,2\},\ S=\{3\},\ W=3 である。ここでタイプ1の被害が3増えると、同じ側へ戻した直後は T={1,2}T=\{1,2\} の被害が4と2になり、W=6W=6 となる。まず種類1と3を交換すると、T={2,3}T=\{2,3\} は小さい側の二種類になるが、W=5W=5 で生存条件を満たさない。そこで種類3を SS へ移す。最終的に T={2}, W=2T=\{2\},\ W=2 となり、次に小さい被害3を足すとちょうど5なので追加できない。必要所持数は1から2へ増える。

この規則では、和を直した後に追加するループは要らない。被害は一種類だけ増えるので、置いていける最大個数は増えず、減っても一個だけである。順序の修復で交換が一回、和の修復で移動が一回で足りる理由を「正当性」で示す。

必要個数の列を、全所持数の答えへ戻す

被害が増えるほど必要所持数 LiL_i は減らない。各 K=0,1,…,MK=0,1,\ldots,M について、答えは

XK=max⁡{i∣0≤i≤N, Li≤K}X_K=\max\{i\mid 0\leq i\leq N,\ L_i\leq K\}

となる。必要数より多くお守りを持っても被害は増えないので、「ちょうど KK 個」という条件にも対応する。

KK を0から増やしながら、討伐数のポインタ pp を0から進める。p<Np<N かつ Lp+1≤KL_{p+1}\leq K の間だけ pp を増やし、その時点の pp を XKX_K とする。ポインタは戻らず、全 KK を合計 O(N+M)O(N+M) 時間で処理できる。

小例として M=3, H=5M=3,\ H=5、モンスターの (Ai,Bi)(A_i,B_i) が順に (1,1),(2,2),(3,3),(3,1)(1,1),(2,2),(3,3),(3,1) なら、上の更新例を含み、L=(0,0,0,1,2)L=(0,0,0,1,2) となる。所持数0では二体、1では三体、2以上では全四体を倒せるので、X=(2,3,4,4)X=(2,3,4,4) である。

典型の発動条件

動的 k-smallest sum の二集合管理

一点更新される非負の重みから、和が上限未満になる最大個数を選ぶときに使う。採用側を小さい順の接頭辞とし、境界の順序・総和・次を追加できない条件を別々に保つ。固定個数の和を求める問題と違い、採用個数そのものの最大性も必要になる。

更新が一個でも、修復が定数回とは限らない。本問では「一種類の増加」と「各種類が個数1に寄与すること」から、最適個数の変化を一個以内に抑えられる。減少更新や重み付きの個数へ、その結論をそのまま移さない。

閾値列の逆引き

長さごとに必要な最小資源を求める方が簡単で、必要資源が長さに対して非減少なら、資源量ごとの最大の長さへ逆引きできる。資源量の昇順に一つのポインタを進めれば、各要素に独立に二分探索するよりもまとめて処理できる。

問題固有の要素

お守りは同じタイプの攻撃をすべて防ぐので、討伐数を固定すれば、各タイプの影響を一つの被害合計へまとめられる。さらに「持つ側」から「置いていく側」へ反転すると、非負の被害を上限未満に詰める個数最大化になる。防げる被害を直接最大化する前に、補集合で制約が単純になるかを見るのが着眼点である。

正当性

ある個数のお守りを置いていくとき、キーが大きい種類を選び、それより小さいキーの種類を選んでいなければ、その二種類を交換しても総被害は増えない。交換を繰り返すと小さい側の接頭辞になるため、各個数における総被害の最小値はその接頭辞の和である。よって、順序・生存・最大性の三条件を満たす TT は、置いていける個数を最大にする。

次に、一種類の正の増加に対する更新を確認する。更新前の最大個数を kk、更新後を k′k' とする。どの選択も被害が減らないので k′≤kk'\leq k である。一方、変更した種類が旧 TT にあれば、それを外した残りの k−1k-1 種類の被害は変わらず、総和も HH 未満である。旧 SS にあれば旧 TT 自体が引き続き選べる。したがって k≥1k\geq1 では k′∈{k−1,k}k'\in\{k-1,k\} であり、k=0k=0 では k′=0k'=0 となる。

手順2の直後も ∣T∣=k|T|=k である。旧 SS のキーを増やした場合は、境界の順序は崩れない。旧 TT のキーを増やした場合、順序を崩せるのはその一キーだけであり、崩れたならそれが TT の最大キーである。これを旧 SS の最小キーと交換すると、残りの旧 TT の全キーは交換で入るキー以下であり、交換で出るキーも残る SS の全キーも、そのキー以上になる。従って手順3の交換一回で、TT は新しい並びの小さい kk 個になる。

その和が HH 未満なら kk 個を選べ、k′≤kk'\leq k と合わせて個数は最大である。和が HH 以上なら、どの kk 個も選べないので k′=k−1k'=k-1 である。手順4で最大キーを一つ外すと、小さい k−1k-1 個になり、その和は選べる k−1k-1 個の中で最小なので HH 未満になる。外した種類を足し直すと直前の和に戻って HH 以上となるため、最大性も満たす。k=0k=0 なら W=0<HW=0<H なのでこの移動は起きない。このように、交換・移動はそれぞれ高々一回で三条件を回復する。

初期状態は三条件を満たし、各更新もこれを回復するため、得られる Li=M−∣T∣L_i=M-|T| は各討伐数の必要最小個数である。被害は非負なので先頭の ii 体までの合計が生存条件を満たせば途中でも生存でき、余分なお守りを持っても被害は増えない。従って、Li≤KL_i\leq K を満たす最大の ii を求める逆引きは、所持数がちょうど KK のときの答えを返す。

実装上の注意

  • 生存判定は W<HW<H とする。W=HW=H でも死亡し、そのモンスターは倒せない。特に H=1H=1 なら、被害0の種類だけが TT に入る。
  • 旧キーを削除してから CbC_b を変更し、元と同じ集合へ新キーを挿入する。種類ごとの所属を配列で記録するか、旧キーを検索して判定する。交換や移動時には所属と WW も更新する。
  • (Cj,j)(C_j,j) をキーにすれば同じ被害の種類も消えない。例えば被害がともに2の種類1と2は (2,1),(2,2)(2,1),(2,2) として保持し、種類1の更新で種類2まで削除しない。
  • 最大・最小キーの参照前に空でないことを確認する。全種類を置いていけるときは SS が空、一種類も置いていけないときは TT が空になる。
  • CjC_j と WW は符号付き64 bit整数で持つ。総被害は最大 N×109≤3×1014N\times10^9\leq3\times10^{14} であり、和の修復前には W≥HW\geq H になることもある。
  • L0=0L_0=0 を含めて保存し、逆引きでは p<Np<N を先に確かめてから Lp+1L_{p+1} を参照する。K=MK=M なら全攻撃を防げるので、必ず XM=NX_M=N となる。

復習の核

  • 資源量ごとの最大到達点が欲しいときは、到達点ごとの必要最小資源を求める向きも考える。
  • 小さい側の接頭辞であることと、上限まで最大個数を取っていることは別条件。「次の一個を足せない」まで確かめる。
  • 一点更新を見たら、最適な個数と境界の要素がそれぞれどれだけ変わるかを調べる。修復回数は、その変化幅から証明する。

計算量と制約

時間

初期の MM キーを一つずつ挿入すると O(Mlog⁡(M+1))O(M\log(M+1))。各モンスターの処理では旧キーの削除・新キーの挿入に加え、交換と移動がそれぞれ高々一回なので O(log⁡(M+1))O(\log(M+1)) 時間かかる。必要数の列から全所持数の答えを求める処理は O(N+M)O(N+M)。全体で O((N+M)log⁡(M+1))O((N+M)\log(M+1)) 時間である。M≤NM\leq N より、O(M+Nlog⁡(M+1))O(M+N\log(M+1)) とも書ける。

空間

全種類の被害・所属と二集合に O(M)O(M)、必要所持数の列に O(N)O(N)、答えの配列に O(M)O(M) を使い、全体で O(N+M)O(N+M)。

制約との対応

1≤M≤N≤3×1051\leq M\leq N\leq3\times10^5、1≤H,Ai≤1091\leq H,A_i\leq10^9、1≤Bi≤M1\leq B_i\leq M。全タイプが入力全体には現れるが、途中の討伐範囲には未登場でもよい。正の攻撃力により被害が単調に増え、最大個数の変化を一個以内に抑えられるため、各回の全種類の並べ直しを避けられる。

出典

公式問題・個別公式解説を2026-10-23に再照合した。三条件を回復する具体的な更新規則と、交換・移動がそれぞれ高々一回となる論証は、本教材で補足した。

分類・前提・執筆情報

掲載状態: 収録済み

Amulets の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: ordered set・multisetの動的順序管理

主題
  • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: ordered set・multisetの動的順序管理

    補助タグ: 貪欲法と交換論 尺取り法・sliding window

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: ordered set・multisetの動的順序管理

    • 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題