CF#312に参加。
あまり解くの早くなかったし、Dもミスったし微妙でした。
http://codeforces.com/contest/558/problem/C
問題
N要素の整数列A[i]が与えられる。
この数列に、以下の処理を繰り返す。
- 1要素の値を倍にする。
- 1要素の値を半分(小数切り捨て)にする。
全要素を同じ値にするのに必要な最小処理回数を求めよ。
解法
まず、全要素を2進数表記したときの共通prefixを求めよう。
解としてあり得るのは、この共通prefixに2の累乗を掛けたものである。
よって、そのような(共通prefix×2の累乗)を総当たりし、処理回数を求めればよい。
int N; int A[101010],B[101010]; vector<int> V; int dodo(int a,int b) { int num=0; while(b%a || ((b/a)&(b/a-1))) num++, a/=2; b/=a; while(b>1) num++, b/=2; return num; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i]; y=A[i]; while(y%2==0) y/=2; V.push_back(y); } sort(V.begin(),V.end()); x=1; while(x*2<=V[0]) x*=2; FOR(i,V.size()) while(V[i]>=x*2) V[i]/=2; while(1) { sort(V.begin(),V.end()); V.erase(unique(ALL(V)),V.end()); if(V.size()==1) break; FORR(r,V) r/=2; } ll mi=10101010; for(int v=V[0];v<=1<<20;v*=2) { ll tot=0; FOR(x,N) tot += dodo(A[x],v); mi=min(mi,tot); } cout<<mi<<endl; }
まとめ
Div2Cにしては少し難しめか?