重み付きマッチング を利用した解法です．

まず，マージするサイズをあらかじめ以下のように決め打ちます．

1. \(1 \times 300 \rightarrow 1 \times 20 + 2 \times 140\)
2. \(1 \times 20 + 2 \times 140 \rightarrow 4 \times 60 + 3 \times 20\)
3. \(4 \times 60 + 3 \times 20 \rightarrow7 \times 20 + 8 \times 20\)
4. \(7 \times 20 + 8 \times 20 \rightarrow 15 \times 20\)
5. \(15 \times 20 \rightarrow 30 \times 10\)

例えば step 1. を \(t=200\) まですべて完了する，と決め打つと次のような問題に帰着されます．

• \(300\) 頂点グラフがある．頂点 \(u, v\) の間には重み \(W_{u,v}\) の辺がある．ここで，\(W_{u,v}\) は \(0\leq t\lt 200\) での \(u,v\) 間の最小距離である．この中からマッチングのペアを \(140\) 個作るとき，最小コストを求めよ．

これは，以下のように言い換えることで重み付きマッチングに帰着します．

• dummy の頂点を \(20\) 個追加する．もともとあった \(300\) 個の頂点と dummy の間の辺の重みは \(0\)，dummy 同士の頂点間の辺の重みは \(\mathrm{inf}\) とする．このグラフで重み最小のマッチングを求めると計 \(160\) 個のペアができる．このうち，両方の頂点がもともとの \(300\) 頂点に含まれるようなもののみをマッチングとして採用するようにする．

これで step. 1 ができました．ほかの step も似たようにして重み付きマッチングに帰着できます．

（例えば step. 2 ではサイズが \(1\) の連結成分同士はマッチングできないが，そのような場合も辺の重みを \(\mathrm{inf}\) とすればよい．）

各 step を \(200\) ずつ時間を使うと決め打つと 807242727 点が獲得できます．

その他自分のやった工夫

• 上の説明では，step. 2 をすべて \(t \in [200,400)\) で行うとしたが，開始時間に関しては \(200\) で固定する必要はなく，step. 1 でのマージ以降とすれよばい．

• そのままマッチングしていくと，速度ベクトルが互いに打ち消し合い，最後の方では各連結成分があまり動かなくなってしまう．したがって，序盤の方の step では速度ベクトルが打ち消されてしまうようなマージにはペナルティを与えるようにすると点数が改善された．

• とにかく序盤で速度ベクトルを失うことの損失が大きいと感じたので，step. 1 は \(t=500\) 程度まで許容し，できるだけ速度ベクトルの損失が少ないかつコストが小さいようなマッチングを目指すことで点数が改善された．