TopCoder SRM 358 Div1 Medium BalanceScale

問題

n個の錘がある。
天秤を使って、これらの錘の重さ全てを量りたい。
n個の中からできるだけ少ない種類の錘をを選んで、n個の重さを全て量れるようにしたい。


同じ種類の錘は何個でも使うことができ、天秤のどちら側に錘をのせても良いものとする。
錘は最低何種類必要か、求めよ。

制約条件

n≦50
錘の重さ≦10000000

方針

まず最初に、全ての錘の重さを最大公約数で割っておく。


x,yの最大公約数が1のとき、ax+by=1を満たすような整数a,bが必ず存在する。
すなわち、最大公約数が1であるような錘の集合を見つければよいことがわかる。


dp[i]を、最大公約数iを作るのに必要な錘の種類の個数とする。
これを更新していくようなdpをすればよい。

ソースコード

計算量をちゃんと見積もってないので嘘DP.最大ケース10msくらい。
本当はビットDPをするのが想定解っぽい。

map<int,int> dp;

class BalanceScale {
	public:
	int takeWeights(vector <int> weight) 
	{
		int n=weight.size(), g=0;
		rep(i,n)g=__gcd(g,weight[i]);
		rep(i,n)weight[i]/=g;
		
		dp.clear();
		rep(i,n)dp[-weight[i]]=1;
		fr(i,dp)rep(j,n){
			int ng=__gcd(-i->first,weight[j]);
			if(!dp.count(-ng)||dp[-ng]>i->second+1)dp[-ng]=i->second+1;
		}
		return dp[-1];
	}
};