TopCoder SRM 728 Div1 Easy Halving

年明け初SRM参加は、なんとかMediumを解きレート微増でした。
https://community.topcoder.com/stat?c=problem_statement&pm=14807

問題

N要素の整数列A[i]が与えられる。
いずれか2以上の整数を1つ選んだ時、その整数を半分にできる。
ただし元の整数aが奇数の場合、(a+1)/2と(a-1)/2どちらを選んでもよい。

A[i]の全要素を等しくするには、半分にする処理を何回行う必要があるか。

解法

各要素について、そこから遷移できる状態はlog(A[i])通りである。
よって各要素に対し、遷移先とそこまでの処理回数を列挙し、全要素から遷移できる状態のうち、処理回数の総和が最小となるものを求めればよい。
全要素処理を繰り返すと1になるので、「全要素から遷移できる状態」は最低1個は存在する。

class Halving {
	public:
	map<int,int> S[101];
	
	void dfs(int i,int a,int step) {
		if(S[i].count(a)) return;
		
		S[i][a]=step;
		if(a%2==0) dfs(i,a/2,step+1);
		else if(a>2) {
			dfs(i,a/2,step+1);
			dfs(i,(a+1)/2,step+1);
		}
	}
	
	int minSteps(vector <int> a) {
		int N=a.size();
		int i;
		FOR(i,N) {
			S[i].clear();
			dfs(i,a[i],0);
		}
		
		int mi=1<<30;
		FORR(x,S[0]) {
			int y=x.first;
			int tot=0;
			FOR(i,N) {
				if(S[i].count(y)) tot+=S[i][y];
				else tot=1<<30;
			}
			mi=min(mi,tot);
		}
		return mi;
		
		
	}
}

まとめ

落ちてる人が意外に多かった。