Codeforces ECR #098 : F. Divide Powers

こういうのどこから手を付けるか悩ましい。
https://codeforces.com/contest/1452/problem/F

問題

2^iがC[i]個からなるmultisetを考える。
ここで以下のクエリを処理せよ。

• 2値pos,valが与えられるので、C[pos]をvalとする。
• 2値x,kが与えられる。multiset中、2より大きな値(2^y)があれば、1手で(2^(y-1))を2個に分割できるとする。(2^x)以下の整数をk個以上作るのに最低何手かかるか。

解法

前者のクエリは、特別な処理を行わず代入するだけでよい。
以下後者のクエリを考える。

• 2^x以下の値2^lは、1回分割すると1個2^x以下の値が増える
• 2^xより大きい値2^lは、(2^(l-x)-1)回分割すると2^xが2^(l-x)個増える、すなわち1個当たりの増分が(2^(l-x))/(2^(l-x)-1)である。ただし、2^lを全部(2^x)以下にしない場合、最低(l-x)回処理しないと(2^x)を得られないので損である。
  • よってlの小さい順に損のない範囲で優先的に分割していこう。

int N,Q;
ll C[35];
ll X,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>C[i];
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			C[x]=y;
		}
		else {
			cin>>X>>K;
			
			ll ret=0;
			ll small=0;
			FOR(i,X+1) {
				small+=((1LL<<i)-1)*C[i];
				K-=C[i];
			}
			
			if(K<=0) {
				cout<<0<<endl;
				continue;
			}
			
			
			
			for(i=X+1;i<N;i++) {
				ll p=1LL<<(i-X);
				ll num=min(K/p,C[i]);
				ret+=num*(p-1);
				small+=num*p*((1LL<<X)-1);
				K-=num*p;
				if(num<C[i]) break;
			}
			
			if(K<=0) {
				cout<<ret<<endl;
				continue;
			}
			
			if(i==N) {
				if(K>small) cout<<-1<<endl;
				else cout<<(ret+K)<<endl;
				continue;
			}
			
			ll mi=1LL<<60;
			for(;i>=X+1;) {
				if(small>=K) mi=min(mi,ret+K);
				ret++;
				i--;
				if(1LL<<(i-X)<=K) {
					ret+=(1LL<<(i-X))-1;
					K-=1LL<<(i-X);
					small+=(1LL<<(i-X))*((1LL<<X)-1);
				}
			}
			cout<<min(mi,ret)<<endl;
			
			
		}
	}
}

まとめ

シンプルな問題ながら結構難しい。