あまり出来の良くなかった回。
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; } } }
まとめ
コードは短いけど、そこそこ時間かかってるな。