Codeforces #633 Div1 A. Powered Addition

調子よかった回みたい。
https://codeforces.com/contest/1338/problem/A

問題

整数列Aが与えられる。
ここで、何度か以下の処理を行う。
i回目の処理では、Aから任意の個数の要素を選び、2^(i-1)を足す。

Aが単調増加となるには、最小何回処理を行えばよいか。

解法

max(A[0...(i-1)])≦A[i]となるようにしたい。
なので、T=max(max(A[0...(i-1)])-A[i])とすると、1+2+4+2^3+....+2^(k-1)≧Tとなる最小のkを求めればよい。

int T;
int N;
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ma=0;
		FOR(i,N) {
			cin>>A[i];
			if(i && A[i]<A[i-1]) {
				ma=max(ma,A[i-1]-A[i]);
				A[i]=A[i-1];
			}
		}
		FOR(i,60) if(ma<1LL<<i) break;
		cout<<i<<endl;
		
		
	}
}

まとめ

ここら辺の難易度は記事書かなくてもいいかもなぁ。