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]; } };