rickytheta's blog

競プロ

AlienDPを理解するだけのログ

理解するだけのログシリーズ

ざっくり

ABC218 HがAlienDPの説明として非常に詳しいです:

https://atcoder.jp/contests/abc218/editorial/2621

問題の整理

  • 個数制約付きの最大化問題がある
  • 個数 → スコア のグラフが上に凸になっている (徐々に伸びが鈍くなる)
    • 個数を変数 x と置いたときのスコアを f(x) と書く
    • ぱっと見で貪欲っぽい雰囲気の問題がこうなりがち
  • 求めたいものはある定数 K=O(N) に対して f(K) だが、普通にDPをすると O(N^2) などかかる
    • 「個数がぴったり K になる」という条件を考えようとすると、DPのキーに個数を持つことになり、更新が O(N) 回なのでトータルで O(NK)=O(N^2) となる

緩和問題と幾何学的解釈

  • 個数を気にする代わりに「1個使うと定数 C だけペナルティがかかる」という緩和問題を考える
    • 元の問題が \max f(K) だったのに対し、 \max f(x)-Cx となっている
    • 最終的な解に使われた個数制約に気をつける必要がなくなり、スコアさえ管理できれば良いので、 o(N^2) で解ける(ことがある)
  • この時の最適解が x=x' に対して f(x')-Cx'=B と求まったとする
    • 移項すると f(x')=Cx'+B となり、これは凸グラフ y=f(x) と直線 y=Cx+B の交点 (x',y':=Cx'+B) を導く
  • B は最大化問題の解なので、この交点 (x',y') は凸グラフ f(x) と交点を持つような傾き C の直線の交点として一番切片の大きい直線上にある
    • 凸グラフと直線の交点であることを考えて、より具体的に書くと、
    • 解周りの3点を P_{-1}(x'):=(x'-1,f(x'-1)), P_0(x'):=(x',f(x')), P_{+1}(x'):=(x'+1,f(x'+1)) として、
    • 線分 P_{-1}(x')P_{0}(x') の傾きを \Delta_-f(x'):=f(x')-f(x'-1)、線分 P_0(x')P_{+1}(x') の傾きを \Delta_+f(x'):=f(x'+1)-f(x') と定義すると、
    • \Delta_-f(x')\ge C \ge \Delta_+f(x') が成り立つ
    • (最大化のイメージ図)

二分探索の構成

  • C をうまく選んで緩和問題を解くことで、 f(K) を求めることを考える
    • \Delta_-f(K)\ge C \ge \Delta_+f(K) となる傾き C を見つけられれば良い
    • この [\Delta_-f(x),\Delta_+f(x)] という範囲は、上に凸なので x に対して広義単調減少 (等号がありえる点に注意)
      • \Delta_+f(x-1)=\ \Delta_-f(x)\ge\Delta_+f(x)\ =\Delta_-f(x+1)
    • ある C に対して \Delta_-f(x)\ge C\ge\Delta_+f(x) を満たす値 x の範囲 [L(C),R(C)] は緩和問題を解くときについでに計算可能(スコアが同一になった際に最小個数・最大個数の2つを保持する)
      • \Delta_-f(L(C))>C>\Delta_+f(R(C)) が成り立つ
      • (以下図であれば L(C)=7,R(C)=10 となる)
    • 元の問題の答えは緩和問題の答えが B=f(x)-Cx であることを考えると f(x)=B+Cx と復元できる
    • つまり、最小個数・最大個数を管理したDPを行うことで、凸包上である傾きの直線が触れるような領域の x の範囲、及びその時の評価値 f(x) の範囲を計算することができる
      • これをクエリとして用いて二分探索を構成する
  • 各 C \ge 0 に対して二分探索することで、 L(C')\le K\le R(C') なる C' を探す
    • 適切な C_{low}\lt C_{high} からスタートし、 L(C_{low})\le R(C_{low})\ \lt K\lt\ L(C_{high})\le R(C_{high}) を維持するように更新する
    • (以下図であれば [L(C_{low}),R(C_{low})]=[0,2],\ [L(C_{high}),R(C_{high})]=[10,\infty]; N=19 とすれば右端は19で切れる)

応用

  • 上記は f(K) を求めるために x の範囲を狭めているが、同時に f(x) の範囲も求められるため、 f(x)=V となるような x を求める、 f(x)\le V となる最大の x を求める、ということも可能
    • 上図であれば [L(C_{low}),R(C_{low})] = [0,2] の時 [f(L(C_{low})),f(R(C_{low}))]=[0,16] のような形
    • f:\mathrm{cost}\mapsto \mathrm{score} だと凸性(連続性)が成り立たない場合、 f の代わりに f':\mathrm{score}\mapsto \mathrm{cost} と言い換えて立式する、としても通せることがある
    • ちなみに f(L\le x\le R) の最大値、という問題は凸性から f(L) または f(R) に帰着されるので、この形は考えなくて良い

提出例

その他

  • 制約の代わりにペナルティ項を添加するという考え方はラグランジュ緩和/ラグランジュ双対が有名
  • LPにおけるラグランジュ緩和・ラグランジュ双対はその先の「任意のペナルティ係数における最大値の最小化問題」を考え、それが元の問題の最適解と一致する、というところが本質
    • 強双対性
  • LPの実行可能解は凸包を成すので、緩和問題の解を考えるのはある傾きの半平面で凸包の表面をなぞる……というところまではイメージは同じ
  • AlienDPは「この傾きの範囲をコントロールすることで、凸包のある条件を満たす領域を二分探索で求める」というのが本質
    • 基本的に凸包は二次元空間で、凸包全体に興味がなく(そもそも凸包でなく凸関数)、一部の定義域または値域にのみ興味がある
  • LPのラグランジュ双対は「この傾きをすべて試して凸包の表面を全部なぞると、元の問題の大域解と一致する」というのが本質
    • 一般に幾何学的解釈はあまり意味がなく、緩和(双対)された結果の問題が既存のグラフ問題で解けるような形になることが重要
  • 制約がスコアに移動して解ける形になる、緩和に使うペナルティ係数の範囲を二分探索/三分探索等でコントロールする、という点では似ている
    • AlienDPはある条件を満たす範囲を求める目的のため
    • LPのラグランジュ双対は \min\max f の \max f がペナルティ係数に対して凸性を持つため(確か)
  • LPの話は以下を参照
  • 本来のAlien Techniqueはグラフの辺の重みにペナルティを添加して、グラフ問題の解に使われる辺の数をコントロールするテクニックを指していたらしい
    • noshi91.github.io
    • グラフ上でこれを行う場合、上記ならmonge性、ICPC2015国内予選Fならマトロイド性、といった「辺の数に対してスコアが凸」という良い性質が必要となる
    • 上記ページではラグランジュ双対として定式化されているが、本ブログやABC解説で書かれている形式は上記ページの「その他」にあたるものと思われる (相互に解釈を変換ができるかは不明……？)
    • (ICPC2015、懐かしすぎますね)