ABC 324 F — Beautiful Path

考察

pathのbeauty/cost比がX以上という条件は、Σ(b_i-c_iX)≥0へ分母を払って加法的なpath weight条件にできる。

全edgeでu_i<v_iなので頂点番号順がtopological orderであり、固定Xでの最大path weightは1回のDAG DPで求められる。

Xを大きくすると全edgeの変換weightが減るため、達成可能性はtrueからfalseへ単調に変わる。

採用する候補: 候補比Xでedge weightをb-cXへ変換し、DAG最大path DPの可否を実数binary searchする。

ratio目的を線形和へ変換し、各判定を全edgeの一走査で行える。

棄却する候補: beauty最大pathとcost最小pathを別々に求め、その比を取る。

2つの最適値を達成するpathが同じとは限らず、ratio最適化にならない。

棄却する候補: 各edgeのb_i/c_iが最大のものを優先してpathを作る。

graphの接続制約と複数edgeの加重平均があり、局所ratioだけでは有効な1→N pathを選べない。

cost総和は正なのでratio不等式を掛け算しても向きが変わらず、変換後weight和の符号だけを見ればよい。

dp[v]=1からvへの最大変換weightとし、到達不能を−∞にすれば、全incoming edge u→vからdp[u]+b-cXをmax更新できる。

predicate(X)ではdp[1]=0、他−∞とし、u=1..Nの番号順に全outgoing edge(u,v,b,c)でdp[v]=max(dp[v],dp[u]+b-cX)を更新し、dp[N]≥0を返す。lower=0、upperを最大b_i/c_i以上に取り、十分な回数binary searchしてtrueならlower=mid、falseならupper=midとしlowerを出力する。

典型の発動条件

発動条件: 正の分母を持つpath上の総和比を最大化するとき。

b-cXへ変換してratio≥Xを加法的可否にする。

DAG longest path DP

発動条件: 負weightも含む有向acyclic graphで最大path和を求めるとき。

topological orderで−∞状態をrelaxする。

発動条件: 連続値Xに対するpredicateが単調で誤差許容出力のとき。

固定回数反復してtrue領域の上端へ収束させる。

問題固有の要素

pathごとに異なるcost総和を分母に持つが、候補Xとの差を各edgeへ分配すると、全pathを同じDAG DPで比較できる。

別の問題へ持ち帰る視点: 平均・比率の最適化は、候補値を引いたweighted sumの正負へ変換できないか試す。

正当性

pathのcost和は正なので比≥xはΣ(b−xc)≥0と同値。頂点番号がtopological順であるためdp最大値は全pathの変換和最大を正確に求める。xを増やすと全pathの和が減るのでpredicateは単調、そのtrue上端が最大比になる。到達不能stateを負無限とすれば存在しないpathは混ざらない。

実装上の注意

  • 到達不能dpからedgeをrelaxせず、long doubleまたは十分な精度のdoubleと大きい負値を使う。
  • 要求誤差10^-9に余裕を持つ反復回数を取り、最後にpredicate true側のlowerを出力する。

復習の核

  • 異なるratioを持つ2本のpathでmidを挟み、変換weight和の符号とbinary search更新方向が元ratio比較に一致するか確認する。

計算量と制約

時間

O(I(N+M))。I回の実数二分探索でDAG DP。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq M \leq 2 \times 10^5; 1 \leq u_i \lt v_i \leq N; 1 \leq b_i, c_i \leq 10^4; There is a path from vertex 1 to vertex N.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: fractional programming・比率parametric search

主題
追加で学ぶ技能
    なし
    既習技能
    • DAGのtopological processing: 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • 単調境界を証明して探索する: 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

    主タグ: fractional programming・比率parametric search

    補助タグ: DAGのtopological processing 単調境界探索

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

    学習の位置

    体系上の位置: fractional programming・比率parametric search

    • 比率候補xをbenefit-x·costの加法目的へ変換し、単調な判定問題を解いて最適比率を求められる。

    先に読む単元:

    • DAGのtopological processing — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、DAGのtopological processingの発動条件・正当化・境界を重複なく学ぶ。
    • 単調境界を証明して探索する — 判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題