ABC 401 G — Push Simultaneously

考察

全員がbuttonへ到着後留まれば同時押下できるため、時間tで可能かはperson-button距離≤tのedgeだけの二部graphにperfect matchingがあるかに等しい。最適bottleneck値はN²個の距離のどれかで、feasibilityはtについて単調である。速度上限1ではt秒以内に到達可能な必要十分条件がEuclidean distance≤tで、trajectory間の干渉はない。候補距離をsortして離散binary searchすれば閾値比較以外に誤差を増やさず、実数binary searchも許容誤差内で可能である。

採用する候補: 距離thresholdを二分探索し、各判定で二部最大matchingを求める

N≤300なのでedgeO(N²)のHopcroft–Karp/DinicをO(log precision)回行うO(N^{2.5}log N)で十分で、bottleneck assignmentを正確に判定できる。

棄却する候補: 各personを最寄りの未使用buttonへgreedy assignする

近いbuttonを誰に譲るべきかが全体Hall条件で決まり、局所最近選択はperfect matchingを失い得る。

全person-button距離をhypotで計算する。mid以下のpairへedgeを張ってmaximum bipartite matching size=Nか判定し、最小feasible thresholdをbinary searchして出力する。

典型の発動条件

bottleneck assignment

発動条件: 一対一対応の最大costを最小化するとき。

cost threshold graphのperfect matching可否を判定する。

Hall条件のalgorithmic判定

発動条件: 各left vertexの候補集合が重なりgreedyで決められないとき。

maximum bipartite matchingを使う。

問題固有の要素

同時性は移動経路のschedulingを生まず、各人が担当buttonへtまでに着けるというstatic bottleneck matchingへ完全に落ちる。

別の問題へ持ち帰る視点: 独立agentの同時到達最小時間は、threshold可到達graph上のassignmentとして考える。

正当性

全員のbutton到着時間をT以下にする割当は距離≤T辺のperfect matchingと同値。Tを増やすと辺が増え可否単調なので二分探索の最小feasible閾値が最小最大到着時間。

実装上の注意

  • 座標差は符号付き広範囲なので浮動小数へ変換してhypotする。threshold等号を含め、matching graphを判定ごとに初期化する。

復習の核

  • N≤7で全permutation assignmentの最大距離最小値と比較し、同距離tie、greedyが失敗する配置、巨大座標を確認する。

計算量と制約

時間

N人Nbutton。距離O(N²)、precision回数B。Hopcroft–Karpを各判定に使って O(BN^(5/2))。

空間

距離と判定二部graph O(N²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 300; 0\leq\mathit{sx} _ i\leq10 ^ {18}\ (1\leq i\leq N); 0\leq\mathit{sy} _ i\leq10 ^ {18}\ (1\leq i\leq N); 0\leq\mathit{gx} _ i\leq10 ^ {18}\ (1\leq i\leq N); 0\leq\mathit{gy} _ i\leq10 ^ {18}\ (1\leq i\leq N); (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{sx} _ j,\mathit{sy} _ j)\ (1\leq i\lt j\leq N); (\mathit{gx} _ i,\mathit{gy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\lt j\leq N); (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\leq N,1\leq j\leq N); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Push Simultaneously の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 二部matching・Hall・Kőnig

主題
  • 二部matching・Hall・Kőnig: 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 二部matching・Hall・Kőnig

    補助タグ: 単調境界探索

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

    学習の位置

    体系上の位置: 二部matching・Hall・Kőnig

    • 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題