kmjp's blog

競技プログラミング参加記です

Codeforces #1055 : D. Division Versus Addition

あまり出来の良くなかった回。
https://codeforces.com/contest/2152/problem/D

問題

整数列Aが与えられる。
クエリとしてAの部分列が指定されるので以下に答えよ。

二人で行うターン制ゲームを考える。

  • 先手は数列の1要素を選択し、2で割って余りを切り捨てることができる。
  • 後手は数列のうち2以上の要素について、1つ選んでインクリメントできる

全要素が1になるまでのターン数を、先手は最小化、後手は最大化したい。
両者最適手を取ると何ターンとなるか。

解法

基本的にA[i]を1にするには、2^n≧A[i]となるnターンかかる。
ただし、例外として2進数表記で100001のようにMSBとLSBの2か所しか立っていない整数のうち、半分だけは選定が先にそれを2で割ることで、1回少ないターンで済ませることができる。

あとは上記の1にするまでにターン数の累積和と、1回少ないターンで済ませられる要素数の累積和を求めておけば、クエリごとにO(1)で解ける。

int T,N,Q;
int A[252525];
int num[252525];
int d2[252525];
ll S[252525];
ll SD[252525];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i];
			num[i]=0;
			while(1<<num[i] < A[i]) num[i]++;
			d2[i]=0;
			if(__builtin_popcount(A[i])==2&&A[i]%2) d2[i]=1;
			S[i+1]=S[i]+num[i];
			SD[i+1]=SD[i]+d2[i];
			
		}
		while(Q--) {
			int L,R;
			cin>>L>>R;
			L--;
			int sum=S[R]-S[L];
			int can=(SD[R]-SD[L]);
			sum-=(can+1)/2;
			cout<<sum<<endl;
		}
	}
}

まとめ

コードは短いけど、そこそこ時間かかってるな。