ABC 319 F — Fighter Takahashi

考察

今倒せる敵を倒すと強さが増え、先へ進める範囲も広がる。敵を倒す順番まで全探索する必要はなく、倒せる敵を尽くしてから、次に飲む薬だけを選べばよい。薬はたかだか10個なので、その使用済み集合を状態にした部分集合DPを考える。

敵を倒し尽くした状態で区切る

頂点 vv の敵を倒すには強さが閾値 svs_v 以上必要で、倒すと gvg_v 増える。薬の頂点では強さが gvg_v 倍になる。いずれも gv≥1g_v\geq 1 であり、強さは減らない。また、訪問済みの頂点間は自由に往復できるため、現在地を状態に含める必要はない。

ただし「今倒せる」とは、強さの条件だけでなく、親まで訪問済みであることも含む。未使用の薬へ初めて入ると必ず飲むので、その薬を使わない間は子孫へ通り抜けられない。

今倒せる敵を後回しにしても、得られる利益はない。加点前の強さを xx、その敵の加点を dd、途中で飲む薬の倍率を m≥1m\geq 1 とすると、加点を先に得た場合は (x+d)m≥xm+d(x+d)m\geq xm+d となる。敵を先に倒すことで後の行動が不可能になることもない。したがって、次の薬を選ぶ前に、未使用の薬を跨がず倒せる敵をすべて倒してよい。

この処理を、到達済みで倒せる敵が一体も残らなくなるまで繰り返す。こうして「追加の薬なしでは、もう敵を倒せない」状態を固定点と呼ぶ。倒すたびに強さと訪問範囲が広がるため、途中で候補を調べ直す必要がある。

本稿では、親まで訪問済みの未討伐の敵を、閾値が最小のものから取り出せる最小heapに入れる。先頭の閾値が現在の強さ以下なら、その敵を取り出して一度だけ加点し、子を新たな候補にする。先頭さえ倒せなければ、他の候補も倒せないので固定点である。薬は敵のheapへ入れず、次に使える薬として待機させ、その子はまだ解禁しない。

独自の小例として、根の子に敵 a ⁣:(sa,ga)=(1,2)a\colon(s_a,g_a)=(1,2) と2倍の薬を置き、薬の子に敵 b ⁣:(sb,gb)=(6,5)b\colon(s_b,g_b)=(6,5) を置く。最初は強さ1から敵 aa を倒して3で止まる。敵 bb は未使用薬の奥なので候補にも入らない。薬を飲むと6になり、初めて子の敵 bb を解禁して倒せるため、次の固定点の強さは11となる。

同じ薬集合では、最大の強さを代表にする

薬の個数を PP とし、各薬に 0,…,P−10,\ldots,P-1 の番号を付ける。使用済み薬集合のbitmaskを mask と呼び、dp[mask] にその集合で到達できる固定点の最大の強さを持たせる。

ここで、強さが大きくても倒した敵が違うなら、一状態へまとめてよいのかが問題になる。弱い固定点の強さを aa、同じ mask の強い固定点の強さを b≥ab\geq a とする。弱い側が倒した敵は、討伐時の閾値がすべて aa 以下であり、そこまでの経路にある薬もすべて使用済みである。強い側はその経路の敵を順に突破できる。もし未討伐の敵が残っていれば、まだ倒せる敵があることになり、固定点であることに反する。

つまり、強い固定点の討伐集合は弱い固定点の討伐集合を含み、弱い側で次に使える薬もすべて使える。さらに、既討伐の敵の加点を二重に得なくても強い側が有利なことは、正当性で確認する。これにより、同じ mask では最大の強さの代表だけを残せる。

薬の倍率だけで飲む順番を決めることはできない。薬への経路が敵に塞がれるうえ、薬と敵の加点の前後関係で最終的な強さが変わるからである。乗算同士は可換でも、途中に加算と到達条件が入るので、異なる薬順をDPで比較する必要がある。

heapと訪問状態を一組で引き継ぐ

強さだけでは次の遷移を実行できないので、各 mask の代表に次を一組で保存する。

  • 強さと討伐済みの敵集合。
  • 親まで訪問済みになった頂点の集合。未討伐の敵や未使用の薬もここに含める。
  • そのうち未討伐の敵を入れた候補heap。

訪問済みなのは根・討伐済みの敵・使用済みの薬である。頂点を初めて訪問したときだけ、その子を到達済みの集合に登録し、子が敵ならheapへ入れる。到達済みでも未訪問の頂点の子は登録しない。これで各敵は一度だけ加点され、未使用薬の奥を先取りすることもない。

初期状態は、強さ1、討伐済み集合は空、根だけ訪問済みとして根の子を登録する。heapで敵を倒し尽くした一組を mask = 0 に保存する。他の状態は到達不能にしておく。

mask を整数の昇順に処理し、到達可能な各状態から、到達済みかつ未使用の薬 jj をすべて試す。新しい集合を next = mask | (1 << j) とすると、遷移は次の順で行う。

  1. mask の強さ・討伐済み集合・到達済み集合・heapをすべてコピーする。別の薬を試すときは、毎回元の状態からコピーし直す。
  2. コピー側で薬 jj を使用済みにし、強さにその倍率を掛ける。
  3. その薬の子を到達済みとして登録し、敵ならheapへ加える。子が別の薬なら待機させる。
  4. コピーしたheap全体で敵を倒し尽くす。倍率によって倒せるようになった別の枝の敵も、以前からheapに残っているので処理できる。
  5. next が到達不能、または新しい強さが dp[next] より大きい場合だけ、強さと補助状態の一組を丸ごと置き換える。

遷移では未使用bitを一つ立てるので、遷移先は必ず現在より大きい。昇順なら、その mask に入るすべての候補を比較してから次へ進める。同じ強さなら任意の一組を残してよい。

いずれかの状態で全敵が討伐済みになれば Yes、全遷移を調べてもなければ No である。全薬を飲むこと自体は目的ではない。

典型の発動条件

少数特殊頂点のbitmask DP

発動条件: 大きいグラフや木の中で、順序選択が必要な特殊操作だけが10個程度のとき。

特殊操作の使用済み集合をbitmaskにし、それ以外を各遷移内で処理する。同じ集合の履歴を一つにまとめるには、代表が他の履歴の将来の選択を再現できることまで証明する。

安全操作のgreedy closure

発動条件: 今できる操作を前倒ししても、後の操作の実行可能性や目的値を損なわないとき。

安全な操作を尽くした固定点で状態を区切り、選択が必要な操作だけを分岐させる。資源が減らないという観察に加え、操作順を交換してよい理由を確認する。

threshold priority queue

発動条件: 候補が逐次解禁され、現在の資源以下の閾値を持つものを処理し尽くしたいとき。

最小の閾値をheapで管理する。候補への到達条件と、取り出して処理できる条件を区別すれば、処理後に子が解禁される依存関係も扱える。

問題固有の要素

木なので、未使用の薬を避けて子孫へ迂回することはできない。一方、処理済み領域内の往復には費用がなく、現在地を忘れてよい。この二つが、到達境界をheapと薬の候補集合で管理できる理由である。

加点は薬より前へ移してよいが、薬を加点より前へ移すと利益が小さくなり得る。単に「どちらも強くなる操作」と見るのでなく、順番を交換したときの不等式を見ると、敵処理と薬の選択を分ける方針へ進める。

正当性

敵の加点を倍率1以上の薬より前に得ても強さは小さくならず、他の頂点への到達も妨げない。したがって、解があれば各薬の使用前に倒せる敵を尽くす形へ変えられる。heapは到達済みの未討伐の敵をすべて保持し、最小の閾値すら満たせないときだけ止まるので、追加の薬なしで倒せる敵を取り残さない。

以下では、強さを上限で打ち切る前の値で考える。同じ使用済み薬集合の二つの固定点について、強さを a≤ba\leq b、討伐集合をそれぞれ A,BA,B とする。AA の敵までの根からの経路には、その薬集合の薬と、閾値が aa 以下の敵しかない。強い側でその経路に未訪問の敵があれば、最初の一体は倒せるので固定点に反する。よって A⊆BA\subseteq B であり、弱い側で到達済みの薬も強い側で到達済みとなる。

加点の二重計上を避けても支配性が保たれることを示す。強い側の履歴で強さがまだ aa 以下の間に倒した敵は、経路上の敵の閾値もすべて aa 以下なので、弱い固定点でも討伐済みである。従って、B∖AB\setminus A の敵はすべて、強い側の強さが初めて aa を超えた後に倒している。その間の薬も強さを減らさないので、

b−a≥∑v∈B∖Agvb-a\geq\sum_{v\in B\setminus A}g_v

が成り立つ。弱い側の今後の操作を強い側でなぞるとき、すでに倒した敵は加点せずに通過する。このとき失う加点の合計は、上の強さの差で賄える。両者が同じ薬を飲めば差は倍率1以上で拡大し、両者にとって未討伐の敵なら同じ加点を得るため、この関係は保たれる。よって弱い側で可能な討伐・薬の使用は強い側でもすべて可能である。途中で強い側だけが倒せる敵を先に倒すことも安全なので、遷移ごとに再び固定点にしてよい。

したがって、各薬集合で最大の強さの一組を残せば十分である。同じ強さの固定点は双方の討伐集合が一致するため、どちらを残してもよい。DPは使用可能な次の薬をすべて試し、実際に可能な操作だけで状態を作る。敵処理の前倒しと状態の置換で解を失わないので、全敵討伐済みの状態が存在することと、元の問題の答えが Yes であることは同値である。

実装上の注意

  • 強さだけを更新して討伐済み集合やheapを以前の代表のまま残すと、その先の加点と到達条件が食い違う。状態は独立にコピーし、改善時は一組で置換する。討伐済みの敵は再びheapへ入れない。
  • 薬は倍率1でも子への通路を開く。強さが増えないことを理由に遷移を省かず、親まで訪問済みかどうかで候補にする。薬が0個なら、初期固定点だけで判定する。
  • 強さの上限を C=max⁡(1,max⁡v: tv=1sv)C=\max(1,\max_{v:\,t_v=1}s_v) とする。敵がいないときは C=1C=1 とする。強さが CC 以上ならすべての敵の閾値を満たし、薬も強さを減らさないので、その先の到達可能性は正確な強さに依存しない。したがって、加点・乗算のたびに CC で打ち切ってよい。打ち切った値が等しくても、固定点の討伐集合は同じ薬集合と閾値条件で決まる。
  • 乗算してから打ち切るのでは遅い。現在の強さを xx、倍率を mm とし、先に x>⌊C/m⌋x>\lfloor C/m\rfloor を調べ、成立すれば結果を CC とする。それ以外のときだけ積を計算し、CC 以下に収める。加点も gv≥C−xg_v\geq C-x なら CC とすれば、途中値のオーバーフローを防げる。

復習の核

  • 全操作順が多いときは、交換して前倒しできる操作を探し、それを尽くした固定点だけで分岐する。
  • 「同じ集合なら最大値だけ残す」前に、処理済み集合の包含と、加点を二重に得なくても将来を再現できる理由を確認する。
  • 強さと、その強さを得た討伐集合・到達境界は一つの状態である。薬の子の解禁と、別の枝に残っていた敵の再判定を両方行う。

計算量と制約

時間

隣接リストと薬の番号付けは O(N)O(N)、初期固定点の処理は O(Nlog⁡N)O(N\log N)。各 mask から試す薬は最大 PP 個で、各遷移は状態のコピーに O(N)O(N)、最大 NN 頂点の登録・heap操作に O(Nlog⁡N)O(N\log N) かかる。従って全体は O(2P(P+1)Nlog⁡N)O(2^P(P+1)N\log N)、P≥1P\geq 1 なら通常の表記で O(2PPNlog⁡N)O(2^PPN\log N) となる。P=0P=0 では初期処理の O(Nlog⁡N)O(N\log N) だけである。

公式解説は前処理で頂点の処理順を整え、1遷移を O(N)O(N) にする別の実装を示している。本稿は各遷移でheapを操作する方式なので、その時間評価とは区別する。

空間

各 mask に討伐済み・到達済み集合とheapをそれぞれ O(N)O(N) で保存し、全体で O(2PN)O(2^PN)。入力の木と、遷移候補を作る一時コピーの O(N)O(N) もこの範囲に収まる。

制約との対応

2≤N≤5002\leq N\leq 500、薬の個数は P≤10P\leq 10 なので、薬集合は最大1024通りで、各集合に最大500頂点分の状態を持てる。親は 1≤pi<i1\leq p_i<i、敵の閾値は 1≤si≤1091\leq s_i\leq 10^9、薬の閾値は0、どちらの増加量・倍率も 1≤gi≤1091\leq g_i\leq 10^9 である。初期強さ1と、加点が正・倍率が1以上という条件が前倒しと支配性の前提となる。強さの打ち切り上限も C≤109C\leq 10^9 に収まる。制限時間は2秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 部分集合・bitmask状態DP

主題
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • 交換論から選択順を導く: 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    主タグ: 部分集合・bitmask状態DP

    補助タグ: 貪欲法と交換論 priority queue・best-first列挙

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

    学習の位置

    体系上の位置: 部分集合・bitmask状態DP

    • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

    先に読む単元:

    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題