kmjp's blog

競技プログラミング参加記です

TopCoder SRM 773 : Div1 Easy ChristmasSongBroadcast

なんだこれ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15866

問題

T個の電波塔とN個の町がある。
ラジオ局から各町にクリスマスソングを配信することを考える。
各町xにはパラメータA[x],B[x]があり、ラジオ局が電波塔yからxに曲を届けるコストは(A[x]*y+B[x]) mod (10^9+7)である。
また、すでに曲を受信した町同士で曲を配信することもでき、そのコストも個別に与えられる。

全町に曲を到達させるのにかかる最小コストを求めよ。

解法

A[x]が100以下なので、ラジオ局から町に曲を届ける最適な電波塔の候補は、(A[x]*y+B[x])がyを増やしていくことでn*(10^9+7)をまたぐ高々A[x]通り程度である。
あとは単なる最小全域木問題を解くだけ。

int D[50][50];
ll C[51];
const ll mo=1000000007;
template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
class ChristmasSongBroadcast {
	public:
	int minimizeCost(int T, vector <int> A, vector <int> B, vector <string> directCost) {
		UF<51> uf;
		
		vector<vector<int>> cand;
		int N=directCost.size();
		int y,x,i;
		FOR(y,N) FOR(x,y) {
			cand.push_back({directCost[y][x],y,x});
		}
		FOR(i,N) {
			ll cur=0;
			ll S=B[i];
			C[i]=B[i];
			while(cur<T) {
				C[i]=min(C[i],S);
				ll add=min(T-cur,(mo-S+A[i]-1)/A[i]);
				S+=add*A[i];
				S%=mo;
				cur+=add;
			}
			cand.push_back({(int)C[i],i,N});
		}
		sort(ALL(cand));
		ll ret=0;
		FORR(c,cand) {
			if(uf[c[1]]!=uf[c[2]]) {
				ret+=c[0];
				uf(c[1],c[2]);
			}
		}
		return ret;
		
	}
}

まとめ

問題のコスト計算の設定が不自然すぎるし、それ以外は単なる最小全域木問題なのであまり楽しめず…。