考察
今倒せる敵を倒すと強さが増え、先へ進める範囲も広がる。敵を倒す順番まで全探索する必要はなく、倒せる敵を尽くしてから、次に飲む薬だけを選べばよい。薬はたかだか10個なので、その使用済み集合を状態にした部分集合DPを考える。
敵を倒し尽くした状態で区切る
頂点 の敵を倒すには強さが閾値 以上必要で、倒すと 増える。薬の頂点では強さが 倍になる。いずれも であり、強さは減らない。また、訪問済みの頂点間は自由に往復できるため、現在地を状態に含める必要はない。
ただし「今倒せる」とは、強さの条件だけでなく、親まで訪問済みであることも含む。未使用の薬へ初めて入ると必ず飲むので、その薬を使わない間は子孫へ通り抜けられない。
今倒せる敵を後回しにしても、得られる利益はない。加点前の強さを 、その敵の加点を 、途中で飲む薬の倍率を とすると、加点を先に得た場合は となる。敵を先に倒すことで後の行動が不可能になることもない。したがって、次の薬を選ぶ前に、未使用の薬を跨がず倒せる敵をすべて倒してよい。
この処理を、到達済みで倒せる敵が一体も残らなくなるまで繰り返す。こうして「追加の薬なしでは、もう敵を倒せない」状態を固定点と呼ぶ。倒すたびに強さと訪問範囲が広がるため、途中で候補を調べ直す必要がある。
本稿では、親まで訪問済みの未討伐の敵を、閾値が最小のものから取り出せる最小heapに入れる。先頭の閾値が現在の強さ以下なら、その敵を取り出して一度だけ加点し、子を新たな候補にする。先頭さえ倒せなければ、他の候補も倒せないので固定点である。薬は敵のheapへ入れず、次に使える薬として待機させ、その子はまだ解禁しない。
独自の小例として、根の子に敵 と2倍の薬を置き、薬の子に敵 を置く。最初は強さ1から敵 を倒して3で止まる。敵 は未使用薬の奥なので候補にも入らない。薬を飲むと6になり、初めて子の敵 を解禁して倒せるため、次の固定点の強さは11となる。
同じ薬集合では、最大の強さを代表にする
薬の個数を とし、各薬に の番号を付ける。使用済み薬集合のbitmaskを mask と呼び、dp[mask] にその集合で到達できる固定点の最大の強さを持たせる。
ここで、強さが大きくても倒した敵が違うなら、一状態へまとめてよいのかが問題になる。弱い固定点の強さを 、同じ mask の強い固定点の強さを とする。弱い側が倒した敵は、討伐時の閾値がすべて 以下であり、そこまでの経路にある薬もすべて使用済みである。強い側はその経路の敵を順に突破できる。もし未討伐の敵が残っていれば、まだ倒せる敵があることになり、固定点であることに反する。
つまり、強い固定点の討伐集合は弱い固定点の討伐集合を含み、弱い側で次に使える薬もすべて使える。さらに、既討伐の敵の加点を二重に得なくても強い側が有利なことは、正当性で確認する。これにより、同じ mask では最大の強さの代表だけを残せる。
薬の倍率だけで飲む順番を決めることはできない。薬への経路が敵に塞がれるうえ、薬と敵の加点の前後関係で最終的な強さが変わるからである。乗算同士は可換でも、途中に加算と到達条件が入るので、異なる薬順をDPで比較する必要がある。
heapと訪問状態を一組で引き継ぐ
強さだけでは次の遷移を実行できないので、各 mask の代表に次を一組で保存する。
- 強さと討伐済みの敵集合。
- 親まで訪問済みになった頂点の集合。未討伐の敵や未使用の薬もここに含める。
- そのうち未討伐の敵を入れた候補heap。
訪問済みなのは根・討伐済みの敵・使用済みの薬である。頂点を初めて訪問したときだけ、その子を到達済みの集合に登録し、子が敵ならheapへ入れる。到達済みでも未訪問の頂点の子は登録しない。これで各敵は一度だけ加点され、未使用薬の奥を先取りすることもない。
初期状態は、強さ1、討伐済み集合は空、根だけ訪問済みとして根の子を登録する。heapで敵を倒し尽くした一組を mask = 0 に保存する。他の状態は到達不能にしておく。
mask を整数の昇順に処理し、到達可能な各状態から、到達済みかつ未使用の薬 をすべて試す。新しい集合を next = mask | (1 << j) とすると、遷移は次の順で行う。
mask の強さ・討伐済み集合・到達済み集合・heapをすべてコピーする。別の薬を試すときは、毎回元の状態からコピーし直す。
- コピー側で薬 を使用済みにし、強さにその倍率を掛ける。
- その薬の子を到達済みとして登録し、敵ならheapへ加える。子が別の薬なら待機させる。
- コピーしたheap全体で敵を倒し尽くす。倍率によって倒せるようになった別の枝の敵も、以前からheapに残っているので処理できる。
next が到達不能、または新しい強さが dp[next] より大きい場合だけ、強さと補助状態の一組を丸ごと置き換える。
遷移では未使用bitを一つ立てるので、遷移先は必ず現在より大きい。昇順なら、その mask に入るすべての候補を比較してから次へ進める。同じ強さなら任意の一組を残してよい。
いずれかの状態で全敵が討伐済みになれば Yes、全遷移を調べてもなければ No である。全薬を飲むこと自体は目的ではない。
典型の発動条件
少数特殊頂点のbitmask DP
発動条件: 大きいグラフや木の中で、順序選択が必要な特殊操作だけが10個程度のとき。
特殊操作の使用済み集合をbitmaskにし、それ以外を各遷移内で処理する。同じ集合の履歴を一つにまとめるには、代表が他の履歴の将来の選択を再現できることまで証明する。
安全操作のgreedy closure
発動条件: 今できる操作を前倒ししても、後の操作の実行可能性や目的値を損なわないとき。
安全な操作を尽くした固定点で状態を区切り、選択が必要な操作だけを分岐させる。資源が減らないという観察に加え、操作順を交換してよい理由を確認する。
threshold priority queue
発動条件: 候補が逐次解禁され、現在の資源以下の閾値を持つものを処理し尽くしたいとき。
最小の閾値をheapで管理する。候補への到達条件と、取り出して処理できる条件を区別すれば、処理後に子が解禁される依存関係も扱える。
問題固有の要素
木なので、未使用の薬を避けて子孫へ迂回することはできない。一方、処理済み領域内の往復には費用がなく、現在地を忘れてよい。この二つが、到達境界をheapと薬の候補集合で管理できる理由である。
加点は薬より前へ移してよいが、薬を加点より前へ移すと利益が小さくなり得る。単に「どちらも強くなる操作」と見るのでなく、順番を交換したときの不等式を見ると、敵処理と薬の選択を分ける方針へ進める。
正当性
敵の加点を倍率1以上の薬より前に得ても強さは小さくならず、他の頂点への到達も妨げない。したがって、解があれば各薬の使用前に倒せる敵を尽くす形へ変えられる。heapは到達済みの未討伐の敵をすべて保持し、最小の閾値すら満たせないときだけ止まるので、追加の薬なしで倒せる敵を取り残さない。
以下では、強さを上限で打ち切る前の値で考える。同じ使用済み薬集合の二つの固定点について、強さを 、討伐集合をそれぞれ とする。 の敵までの根からの経路には、その薬集合の薬と、閾値が 以下の敵しかない。強い側でその経路に未訪問の敵があれば、最初の一体は倒せるので固定点に反する。よって であり、弱い側で到達済みの薬も強い側で到達済みとなる。
加点の二重計上を避けても支配性が保たれることを示す。強い側の履歴で強さがまだ 以下の間に倒した敵は、経路上の敵の閾値もすべて 以下なので、弱い固定点でも討伐済みである。従って、 の敵はすべて、強い側の強さが初めて を超えた後に倒している。その間の薬も強さを減らさないので、
が成り立つ。弱い側の今後の操作を強い側でなぞるとき、すでに倒した敵は加点せずに通過する。このとき失う加点の合計は、上の強さの差で賄える。両者が同じ薬を飲めば差は倍率1以上で拡大し、両者にとって未討伐の敵なら同じ加点を得るため、この関係は保たれる。よって弱い側で可能な討伐・薬の使用は強い側でもすべて可能である。途中で強い側だけが倒せる敵を先に倒すことも安全なので、遷移ごとに再び固定点にしてよい。
したがって、各薬集合で最大の強さの一組を残せば十分である。同じ強さの固定点は双方の討伐集合が一致するため、どちらを残してもよい。DPは使用可能な次の薬をすべて試し、実際に可能な操作だけで状態を作る。敵処理の前倒しと状態の置換で解を失わないので、全敵討伐済みの状態が存在することと、元の問題の答えが Yes であることは同値である。
実装上の注意
- 強さだけを更新して討伐済み集合やheapを以前の代表のまま残すと、その先の加点と到達条件が食い違う。状態は独立にコピーし、改善時は一組で置換する。討伐済みの敵は再びheapへ入れない。
- 薬は倍率1でも子への通路を開く。強さが増えないことを理由に遷移を省かず、親まで訪問済みかどうかで候補にする。薬が0個なら、初期固定点だけで判定する。
- 強さの上限を とする。敵がいないときは とする。強さが 以上ならすべての敵の閾値を満たし、薬も強さを減らさないので、その先の到達可能性は正確な強さに依存しない。したがって、加点・乗算のたびに で打ち切ってよい。打ち切った値が等しくても、固定点の討伐集合は同じ薬集合と閾値条件で決まる。
- 乗算してから打ち切るのでは遅い。現在の強さを 、倍率を とし、先に を調べ、成立すれば結果を とする。それ以外のときだけ積を計算し、 以下に収める。加点も なら とすれば、途中値のオーバーフローを防げる。
復習の核
- 全操作順が多いときは、交換して前倒しできる操作を探し、それを尽くした固定点だけで分岐する。
- 「同じ集合なら最大値だけ残す」前に、処理済み集合の包含と、加点を二重に得なくても将来を再現できる理由を確認する。
- 強さと、その強さを得た討伐集合・到達境界は一つの状態である。薬の子の解禁と、別の枝に残っていた敵の再判定を両方行う。
計算量と制約
時間
隣接リストと薬の番号付けは 、初期固定点の処理は 。各 mask から試す薬は最大 個で、各遷移は状態のコピーに 、最大 頂点の登録・heap操作に かかる。従って全体は 、 なら通常の表記で となる。 では初期処理の だけである。
公式解説は前処理で頂点の処理順を整え、1遷移を にする別の実装を示している。本稿は各遷移でheapを操作する方式なので、その時間評価とは区別する。
空間
各 mask に討伐済み・到達済み集合とheapをそれぞれ で保存し、全体で 。入力の木と、遷移候補を作る一時コピーの もこの範囲に収まる。
制約との対応
、薬の個数は なので、薬集合は最大1024通りで、各集合に最大500頂点分の状態を持てる。親は 、敵の閾値は 、薬の閾値は0、どちらの増加量・倍率も である。初期強さ1と、加点が正・倍率が1以上という条件が前倒しと支配性の前提となる。強さの打ち切り上限も に収まる。制限時間は2秒、メモリ制限は1024 MiB。
出典