M-SOLUTIONS 2020 E - M's Solution

問題

座標平面上に置かれた $n$ 個の点について，重み $P _ i$ と 座標 $(X _ i, Y _ i)$ をもつとし，点 $i$ から最も使い直線との距離を $D _ i$ とする．直線 $X = 0, Y = 0$ がある状態から始めて，各 $k = 0, \ldots, n$ について，$X$ 軸または $Y$ 軸に平行な直線を $k$ 本追加したときの $\sum _ {i} D _ i \times P _ i$ の最小値を求めよ．($n \leq 15$)

atcoder.jp

解説

直線を追加する際，どの点も通らないような直線を追加するなら最も近い点を通るようにしたほうがいいので，追加する直線はすべていずれかの点を通るものとして考える．また，ある点を通る直線を追加したら，その点は存在しなくなったと考えていいので，同じ点を通る直線は $1$ 本まででよい．以上の考察から，各点について

• その点を通る直線を引かない
• その点を通り $X$ 軸に平行な直線を引く
• その点を通り $Y$ 軸に平行な直線を引く

の $3$ 通りの選択肢があるので，$3 ^ n$ 通りを全探索し，直線の本数の合計が $k$ だったとき，$k$ に対する最小値を更新していけばよい．

実装

提出コード

点の集合 $s$ に対して，$s$ に属する点を通り $X$ 軸に平行な直線を引いたときの点 $i$ から最も近い $X$ 軸に平行な直線への距離 $\times P _ i$ を $DX[s][i]$ とする．$DY[s][i]$ も同様に定義する．

全探索では，まず $X$ 軸に平行な直線を引く点の集合 $sx$ を決め，その補集合から $Y$ 軸に平行な直線を引く点の集合 $sy$ を決める．

直線の本数の合計を計算する際，$2$ 進数表示したときの $1$ の数を数えるが，これは前計算しておくことで効率が上がる．(これをしないと実行時間制限に引っかかる．)

n = int(input())
X, Y, P = [], [], []
for i in range(n):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = [[0] * n for s in range(1 << n)]
DY = [[0] * n for s in range(1 << n)]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(1 << n)]
A = [10**20] * (n + 1)
for sx in range(1 << n):
    rx = ((1 << n) - 1) ^ sx
    sy = rx
    for _ in range(1 << (n - BC[sx])):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")