Codeforces #1116 : Div1. D. How Long Until Nothing Remains?

気付いてしまうと楽だったんだけどね。
https://codeforces.com/contest/2255/problem/D

問題

正整数列Aが与えられる。
以下を繰り返しAの全要素を0にするのにかかる最小処理回数を求めよ。

• 1要素A[i]を選ぶ。
  • A[i]は2で割って小数点以下を切り捨て、他の要素は2で割って小数点以下を切り上げる。

解法

この問題は以下のように読み替えられる。

• n回目の処理では、任意の要素を2^(n-1)だけ減らす。
• 全要素を0以下にするのにかかる最小処理回数を求めよ。

max(A[i])＜2^30のため、Aを昇順にソートしたとき、31要素目以降は常に1回で0以下にできる。
よって、Aの小さい順に30要素を最小何回で0以下にできるかを判定する。

最大でも60回あれば全要素0以下にできる。
よってその回数を総当たりしよう。
Aの専用30要素のうち、残された最大要素から2^(n-1)をnの大きい順に引くことを繰り返せばよい。

int T,N,A[202020];

int ok(vector<ll> B,int id) {
	while(id--) {
		sort(ALL(B));
		if(B.back()<=0) return 1;
		B.back()-=1LL<<id;
		
	}
	sort(ALL(B));
	if(B.back()<=0) return 1;
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
		}
		sort(A,A+N);
		vector<ll> B;
		FOR(i,min(N,30)) B.push_back(A[i]);
		int ret=0;
		for(i=B.size();i<=60;i++) if(ok(B,i)) {
			ret=i+N-B.size();
			break;
		}
		
		
		cout<<ret<<endl;
		
	}
}

まとめ

2で割る系の問題はこの言い換えを覚えておかないとな。