Hello 2025 : F. Formation

落ち着けば思いついたのかなぁ。
https://codeforces.com/contest/2057/problem/F

問題

整数列Aが与えられる。
初期状態で、A[i]*2≧A[i+1]を満たす。

以下のクエリにそれぞれ答えよ。

• Aの要素を、合計でK回インクリメントできるとする。A[i]*2≧A[i+1]を満たすようにした場合、Aの最大値を最大化せよ。

解法

A[i]+Kは高々2^31以下なので、A[i]を最大化しようとする場合、インクリメントすべきはA[i-30]-A[i]の範囲に収まる。
もしA[i-k],...,A[i]に対しA[j]*2=A[j+1]を満たしている場合、A[i]をX回インクリメントするにはA[i-x]を(X>>x)回インクリメントしなければいけない。

ここから、i,kを総当たりすることで、A[i-k],...,A[i]に対しA[j]*2=A[j+1]を満たしている状態を作るまでのインクリメント回数と、A[i-k-1]をインクリメントせずに済むKの範囲が求まる。
これらの範囲をソートしつつ、各クエリについて回答していく。

int T,N,Q;
ll A[50505];
ll K[50505];
ll ret[50505];
pair<ll,ll> C[32];
vector<array<ll,4>> ev;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		A[0]=1LL<<32;
		ev.clear();
		for(i=1;i<=N;i++) {
			cin>>A[i];
			ll sum=0;
			for(k=0;k<=32;k++) {
				sum+=A[i-k];
				ll start=A[i-k]*((2<<k)-1)-sum;
				if(start>1<<30) break;
				ll end=A[i-(k+1)]*((4<<k)-1)-(sum+A[i-(k+1)]);
				ev.push_back({start,-1,k,sum});
				ev.push_back({end,1,k,sum});
			}
		}
		FOR(i,Q) {
			cin>>K[i];
			ev.push_back({K[i],0,i,0});
		}
		multiset<ll> S[33];
		sort(ALL(ev));
		FORR(a,ev) {
			if(a[1]==-1) {
				S[a[2]].insert(a[3]);
			}
			else if(a[1]==1) {
				S[a[2]].erase(S[a[2]].find(a[3]));
			}
			else {
				x=a[2];
				ll cur=0;
				for(i=30;i>=0;i--) {
					ll tmp=cur+(1<<i);
					ll now=tmp;
					ll need=0;
					FOR(j,32) if(S[j].size()) {
						ll v=*S[j].rbegin();
						need+=now;
						now=(now+1)/2;
						if(need-v<=a[0]) break;
					}
					if(j<32) cur=tmp;
				}
				ret[x]=cur;
			}
		}
		FOR(i,Q) cout<<ret[i]<<" ";
		cout<<endl;
	}
	
}

まとめ

言われてみるとシンプルだけど、最初からこれを思いつける気がしない。