M-SOLUTIONS プロコンオープン 2020 : E - M's Solution

遅刻参加だけど、解いた時間だけ見ると35分程度で優勝と同じぐらいだ…まぁ2WAしてるのであんまり意味ないけど。
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_e

問題

2次元座標上で初期状態でX軸とY軸の位置に道路がある。
ここに、X軸またはY軸に平行な道路をK本追加することを考える。

この座標上でN個の町があり、その座標と人口が与えられる。
K本の道路を作ったとき、各人の最寄りの道路までの距離の総和の最小値を求める、ということをK=0～Nについてそれぞれ答えよ。

解法

K本は、各町のX座標かY座標に一致させるのがよい。
また、同じ町を通る道路はX軸かY座標片方で良い。

そこで、(X座標の道路を通す町, Y座標の道路を通す町, どちらも通らない町)の組み合わせを3^N通り総当たりし、それぞれ最小値を求めよう。
前処理として、X座標とY座標の集合に対し、各町からの最短距離がどうなるか求めておくとよい。

int N;
int X[15],Y[15],P[15];
ll ret[16];

ll xmin[1<<15][15];
ll ymin[1<<15][15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>P[i];
	}
	FOR(i,N+1) ret[i]=1LL<<60;
	
	FOR(i,1<<N) {
		FOR(j,N) {
			xmin[i][j]=abs(X[j])*1LL*P[j];
			ymin[i][j]=abs(Y[j])*1LL*P[j];
			FOR(x,N) if(i&(1<<x)) {
				xmin[i][j]=min(xmin[i][j],abs(X[j]-X[x])*1LL*P[j]);
				ymin[i][j]=min(ymin[i][j],abs(Y[j]-Y[x])*1LL*P[j]);
			}
		}
	}
	
	
	for(int xmask=0;xmask<1<<N;xmask++) {
		int lef=((1<<N)-1)^xmask;
		for(int ymask=lef; ymask>=0; ymask--) {
			ymask&=lef;
			ll sum=0;
			FOR(i,N) sum+=min(xmin[xmask][i],ymin[ymask][i]);
			y=__builtin_popcount(xmask|ymask);
			ret[y]=min(ret[y],sum);
		}
	}
	
	FOR(i,N) ret[i+1]=min(ret[i],ret[i+1]);
	FOR(i,N+1) cout<<ret[i]<<endl;
	
	
}

まとめ

普通に参加すればよかったかな。