ABC 394 G — Dense Buildings

考察

高さXのwalkwayだけで二building間を移動できるのは、高さX以上のcellだけを残したgridで両cellが連結なことと同値である。

二cellが連結でいられる最大threshold Mが分かれば、実際に使う高さはmin(M,Y,Z)で、階段回数はY+Z-2min(M,Y,Z)になる。

採用する候補: 隣接edgeのcapacity=min(F_u,F_v)でthreshold connectivityをDSU処理し、全queryをparallel binary searchする

高さmidでの連結判定をquery間で共有し、各roundにedgeを降順追加する一回のDSU sweepで全queryを更新できる。

棄却する候補: queryごとに高さを二分探索し、その都度grid BFSする

一判定O(HW)をQ logF回行い、最大2×10^5 queryでは不可能である。

thresholdを下げるほど利用可能cell/edgeが増えるのでconnectivityは単調である。

edge capacityは両端buildingの低い方で、その高さ以下なら同階walkwayを渡れる。

全grid隣接edgeをcapacity降順にsortする。各queryの[L,R) thresholdを持ち、mid別bucketを作るroundごとにDSUを初期化してedgeをthresholdまで追加し、endpoint連結ならL=mid、否ならR=midと更新する。確定Mから式を出力する。

典型の発動条件

offline dynamic connectivity by threshold

発動条件: edgeがkey threshold以下/以上で単調に追加され、多数のpair接続閾値を求めるとき。

edge sortとDSU sweepを共有する。

発動条件: 多数queryが同じ単調更新列上でbinary searchするとき。

同じmid判定を一roundのdata structure sweepへまとめる。

問題固有の要素

walkway回数は無料なのでpath長でなく「path上の最小building高さを最大化するwidest path」だけがstairs最小化を決める。

別の問題へ持ち帰る視点: 移動costが高度を一度下げて戻す形なら、空間部分はbottleneck connectivityへ分離する。

正当性

ある高さで連結なら、その経路を同じ階で渡れる。逆により高い階で渡る経路があれば、その高さの辺だけで両端が連結になる。したがって連結閾値が利用可能な最高階を決め、両端の階で上限を付けた階段回数の式が最小になる。

実装上の注意

  • same cell queryでもfloorが異なるcaseはMをbuilding高さ相当として式が成り立つ。mid bucket処理のedge≥mid境界とL/R初期値を統一する。

復習の核

  • 小gridで全threshold BFSとmax-min pathを列挙し、同cell、隣接cell、start/end floorがbottleneckより低いcaseを比較する。

計算量と制約

時間

O(E log E+log Hmax·(Eα(V)+Qα(V)+Q log Q))、V=HW,E=O(V)、midをsortするPBS版。

空間

O(V+Q)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 1\leq H \leq 500; 1\leq W \leq 500; 1\leq F_{i,j} \leq 10^6; 1\leq Q\leq 2\times 10^5; 1\leq A_i,C_i\leq H; 1\leq B_i,D_i\leq W; 1\leq Y_i\leq F_{A_i,B_i}; 1\leq Z_i\leq F_{C_i,D_i}; (A_i,B_i,Y_i)\neq (C_i,D_i,Z_i); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Dense Buildings の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: parallel binary search・多数境界の判定共有

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: parallel binary search・多数境界の判定共有

    補助タグ: DSUによる連結成分管理・縮約 event・値順のオフライン走査 単調境界探索

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

    学習の位置

    体系上の位置: parallel binary search・多数境界の判定共有

    • 各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • event順にactive集合を更新する — 値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。
    • 単調境界を証明して探索する — 判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題