単調境界を証明して探索する

概要

単調境界探索

答えの候補を一つ決めると、その候補で条件を満たせるかは調べやすいことがある。候補を順に並べたとき、判定結果が一度だけ切り替わるなら、全候補を試す代わりにその境界を二分探索できる。

考え方

数値を並べて、真偽が変わる場所を見る

ABC269 Eでは、ルークのない行と列を別々に探せる。行だけに注目すると、各行にはルークが高々一つあり、空の行はちょうど一つである。そこで「先頭から xx 行にあるルークの個数は xx 未満か」を判定 P(x)P(x) とする。これは、その範囲に空の行が含まれることと同値である。

説明用に7行のうち4行目が空なら、次の真偽列になる。

調べる行数 xxルークの個数判定 P(x)P(x)
11偽
22偽
33偽
43真
54真
65真
76真

一度空の行を含めば、さらに行を増やしても空の行を含んだままである。従って最初の真が空の行番号になる。列も同じ考え方で探せる。

最適化でも同様に、例えば「予算 xx 以内で要求を満たせるか」と問う。可能な計画は予算を増やしても使えるので、真の後に偽へ戻らない。ただし、元の要求と判定が同値であることと、候補値に対して判定が単調であることは別々に示す。誤った判定器が単調でも、元の問題の答えは求まらない。

最初の真を挟む二つの端点

整数候補の範囲を a≤x≤ba\leq x\leq b とし、判定は偽から真へ変わるとする。範囲のすぐ外に番兵 lo=a−1lo=a-1、hi=b+1hi=b+1 を置き、意味上 P(lo)=falseP(lo)=\mathrm{false}、P(hi)=trueP(hi)=\mathrm{true} と定める。番兵は「その側まで探しても答えがない」ことを表す印で、判定器には渡さない。

hi−lo>1hi-lo>1 の間、中央の整数を

mid=lo+⌊hi−lo2⌋mid=lo+\left\lfloor\frac{hi-lo}{2}\right\rfloor

として判定する。真なら hi=midhi=mid、偽なら lo=midlo=mid とする。小例では初期値 (lo,hi)=(0,8)(lo,hi)=(0,8) から、4は真なので (0,4)(0,4)、2は偽なので (2,4)(2,4)、3は偽なので (3,4)(3,4) となって止まる。

常に左端は偽、右端は真であり、単調性から最初の真は (lo,hi](lo,hi] に残る。更新後もこの不変条件を保ち、幅がほぼ半分になる。終了時は両端が隣り合うため、hihi が最初の真である。

  • 範囲内が全真なら hi=ahi=a となる。
  • 範囲内が全偽なら hi=b+1hi=b+1 となり、答えなしと分かる。

真から偽へ変わる判定で「最後の真」を求めるなら、真偽を反転した判定で最初の真を探し、その一つ前を返せる。この場合も全偽なら答えなし、全真なら bb となる。同じ境界規約へ直してから実装すると、どちら側を返すかが曖昧にならない。

単調性の前に、等号を含む判定式を確定する

境界の探し方が決まっても、判定式の等号は問題の条件から導く必要がある。ABC373 Eのように「自分の当選を必ず保証する」問題では、敵対者が落選させる最小費用を考えるとよい。

残っている票の総数を RR、自分へ追加する票を xx、その後に敵対者が失敗例を作る最小費用を C(x)C(x) とする。敵対者の予算は R−xR-x なので、C(x)≤R−xC(x)\leq R-x なら失敗可能、C(x)>R−xC(x)>R-x なら保証可能である。費用が予算と等しいときも、敵対者は必要な票を配れる。

自分の最終得票を tt、ある相手の現在得票を vv とする。相手を tt より真に大きくする費用は max⁡(0,t+1−v)\max(0,t+1-v) であり、正の費用が必要なのは v≤tv\leq t の相手である。例えば t=5,v=5t=5,v=5 でも1票必要になる。従ってソート列の境界は upper_bound(t)、整数なので同じ位置を指す lower_bound(t+1) である。

同値要素だけの入力、残資源0、費用と資源がちょうど等しい場合を確認してから、この判定の単調性を証明する。

成立条件と計算量

整数候補数を U=b−a+1U=b-a+1、一回の判定費用を TT とすると、判定回数は O(log⁡(U+1))O(\log(U+1))、探索時間は O(Tlog⁡(U+1))O(T\log(U+1)) である。ソートや累積和などの前処理は別に加える。探索自体の追加空間は O(1)O(1) だが、判定器と前処理で使う領域は別途必要になる。

使う前に、判定の同値性、候補値の単調性、探索範囲を確認する。貪欲法を判定器にするなら、その貪欲法が実現可能性を正しく答える証明も必要である。試した候補の処理結果が次の判定へ残らないようにし、端点・差・中央を計算できる整数型を選ぶ。実数探索では隣接整数で停止できないため、必要な誤差と反復回数を別に定める。

問題一覧では、ABC269 Eで問い合わせから真偽を得る例、ABC270 Eで完全周回数に対する最後の成功を探す例へ進む。後者は全消費時に成功がいつまでも続くため、その場合を先に処理して有限の探索範囲を作る。ABC373 Eでは、さらに等号を含む判定式の設計を学ぶ。境界探索と判定器の設計を分けて読み返そう。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。二分探索の実装に加え、判定の単調性と境界の意味を説明する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-monotone-search

習得する技能

  • 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: fractional programming・比率parametric search、parallel binary search・多数境界の判定共有。

判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。

このUnitでは扱わないもの

  • 連続窓の両端を一方向に進める尺取り法、および真偽判定の単調境界を持たない三分探索・局所探索。

根拠