M-SOLUTIONS プロコンオープン 2020 E. M's Solution
問題
グリッド上に、N個の都市があり、i番目の都市は、(X_i, Y_i)に位置する。また、都市の人工はP_iで与えられる。
今、x=0とy=0に鉄道が走っており、x軸またはy軸に平行なK本の鉄道を追加で建設できる。
各都市の人々は、一番近い鉄道まで、グリッドに沿って歩くことになる。
K=0～Nについて、鉄道を最適に建設した場合の人々の歩く距離の合計の最小値を答えよ。
制約
- 1 <= N <= 15
- -10000 <= X_i, Y_i <= 10000
- 1 <= P_i <= 1000000
- 各都市の位置はすべて異なる
解法
x軸方向だけ考えてみる。
x座標について、鉄道を最適に作る場合というのは、都市のあるx座標のどれかになる。
(各人レベルに分解して考えるとΣ|A_i-x|の最小値を求めたいが、これは最適値が中央値になる)
よって、鉄道を建設するのは、各都市の座標だけ考えれば良い。
x軸とy軸方向に、N通り建設の仕方があるが、それぞれ全探索を考える。
ただし、合計はK本しか引けないので、x軸でi本建設したらy軸ではK-i本しか使えない。
また、同じ都市について、その都市については1つでも鉄道が通っていれば歩く距離は0になるので、x軸でもy軸でも鉄道を建設するのは意味はない。(他の都市を選んでたまたま鉄道が通るのは構わない)
したがって、N個の都市について、x軸に鉄道を建設、y軸に鉄道を建設、鉄道を建設しないの3通りを考える。
この列挙は、bit演算でO(3^N)でできることが知られている。
よって、各軸で鉄道を引く座標が与えられるので、各都市から見て鉄道までの最小の距離を求めればよい。
しかし、これに毎回O(N^2)かけてしまうと、TLEしてしまう。
これは、前処理で、O(2^N * N^2)で各軸について、その都市を選んだ場合のその軸での
鉄道までの最小距離、というのをN個の都市について求めてメモしておけば、O(N)で計算でき、最終的にO(N * 3^N)の計算量で求められる。
