Codeforces #572 Div1 D. Make Equal

この発想は思いつかんなぁ…。
https://codeforces.com/contest/1188/problem/D

問題

N要素の整数列Aが与えられる。
1回の処理で、1要素に2の累乗である正整数を加算できるとする。
Aの全要素の値をそろえるのに必要な最少処理回数を求めよ。

解法

Aが昇順にソート済みとする。仮にそろえた値をT+A[N-1]とする。
B[i]=A[N-1]-A[i]とすると、i番目の要素はT+B[i]だけ加算するようにしたい。
bits(x) := xの2進数表記で1の立つ桁数
とすると、sum(bits(T+B[i]))を最小化するTを求める問題になる。

同じ値を2回足す意味はないので、結局1～2^60までの2の累乗値を、足すかたさないかという問題となる。
2^jをjの小さい順に見ていくことを考える。

今2^0～2^(j-1)まで足すかどうか決めたとき、値をそろえるにはAのうち各j bit目が立っているもの全体にさらに2^jを足して0にそろえるか、たっていないものに足して1にそろえるかである。
2^0～2^(j-1)のパターンを全部列挙することは時間的にできないが、要は2^0～2^(j-1)までを足すかどうか決めたことによって、下位のbitから何個繰り上がりが発生しているかだけわかれば、上記処理は行える。
よって各桁について繰り上がりが0～N個の場合を列挙すればよく、O(N・log(max(A))で済む。

int N;
ll A[101010];

ll dp[101010][62];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N) A[i]=A[N-1]-A[i];
	sort(A,A+N);
	FOR(i,N+1) FOR(j,62) dp[i][j]=1LL<<60;
	dp[0][0]=0;
	FOR(i,60) {
		vector<pair<ll,ll>> V;
		FOR(j,N) V.push_back({A[j]&((1LL<<i)-1), A[j]});
		sort(ALL(V));
		vector<int> C[2];
		C[0].push_back(0);
		C[1].push_back(0);
		FOR(j,N) {
			C[0].push_back(C[0].back());
			C[1].push_back(C[1].back());
			C[(V[j].second>>i)%2].back()++;
		}
		int T[2]={C[0].back(),C[1].back()};
		FOR(j,N+1) { // num of carry
			int n1,carry;
			// 0
			n1=C[1][N-j]+C[0][N]-C[0][N-j];
			carry=C[1][N]-C[1][N-j];
			dp[carry][i+1]=min(dp[carry][i+1],dp[j][i]+n1);
			// 1
			n1=C[1][N]-C[1][N-j]+C[0][N-j];
			carry=N-C[0][N-j];
			dp[carry][i+1]=min(dp[carry][i+1],dp[j][i]+n1);
		}
	}
	
	cout<<dp[0][60]<<endl;
	
}

まとめ

聞いてしまえばシンプルだけど、自分では思いつかないなぁ。