考察
全員が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.
出典