CADDi 2018 : E - Negative Doubling

結構手間取ってしまった。
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

問題

N要素の整数列Aが与えられる。
任意の要素を-2倍する、という処理を繰り返したとき、全体が単調増加になるようにするのに必要な処理の最小値を求めよ。

解法

処理後、A[x]が負でA[x+1]が正となるようなxを総当たりすることを考える。
(全要素負・全要素正も同様に行う)

A[x+1],A[x+2],...はいずれも正でなければならないので、4倍することを繰り返して単調増加にならなければならない。
A[x],A[x-1],A[x-2],...は、最後に-2倍することを考えると、最後の-2倍を除けば、やはり4倍することを繰り返して単調増加にならなければならない。

よって、A[x+1]以降を単調増加にするのに必要な処理回数R[x+1]および、A[x]以前を逆向きに単調増加にするのに必要な処理回数L[x]をそれぞれ求める。
以下R[x+1]がわかっているとき、R[x]を求めることを考える。(Lについても逆向きに同様に行えばよい)
A[x]以降、A[y]＞A[y+1]である限り、A[y+1]を4倍する、ということを繰り返そう。
これを繰り返すと、A[y+1]を4倍したことでA[y+2]も4倍しないといけなくなり…となる可能性がある。
ただし、途中A[y]＞2^30程度になると、A[y]以降はA[y]とA[y+1]は４倍未満の差となるはずである。
よって、そのようなA[y]以降は1回ずつ4倍すればよいの4倍すべき回数はわかる。

15回も4倍すればA[y]は2^30以上になるので、均しではyを辿る回数はO(N)で済む。

int N;
ll A[201010];
int L[202020];
int R[202020];
ll LSS[202020];
ll RSS[202020];

ll B[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N) B[i]=A[i];
	for(i=N-2;i>=0;i--) {
		LSS[i]=LSS[i+1];
		while(1) {
			x=lower_bound(B+i+1,B+N,B[i])-B;
			if(x==i+1) break;
			for(j=i+1;j<x;j++) {
				B[j]*=4;
				LSS[i]+=2;
			}
			for(j=x;j<N;j++) {
				if(B[j]>1LL<<40) {
					LSS[i]+=(N-j)*2;
					break;
				}
				if(B[j]>=B[j-1]) break;
				B[j]*=4;
				LSS[i]+=2;
			}
		}
	}
	FOR(i,N) B[N-i-1]=A[i];
	for(i=0;i<N;i++) {
		if(i) RSS[i]=RSS[i-1];
		RSS[i]++;
		while(1) {
			x=lower_bound(B+(N-1-i)+1,B+N,A[i])-B;
			if(x==(N-1-i)+1) break;
			for(j=(N-1-i)+1;j<x;j++) {
				B[j]*=4;
				RSS[i]+=2;
			}
			for(j=x;j<N;j++) {
				if(B[j]>1LL<<40) {
					RSS[i]+=(N-j)*2;
					break;
				}
				if(B[j]>=B[j-1]) break;
				B[j]*=4;
				RSS[i]+=2;
			}
		}
	}
	
	
	
	ll mi=LSS[0];
	
	for(i=1;i<N;i++) {
		ll tot=LSS[i]+RSS[i-1];
		mi=min(mi,tot);
	}
	cout<<mi<<endl;
}

まとめ

最初まんまと想定？誤解法にはまってしまった。