Codeforces #608 Div2 E. Common Number

6問回とは言え、Div2Eの割に簡単？
https://codeforces.com/contest/1271/problem/E

問題

関数f(x)を以下のように置く。

• xが偶数の時f(x)=x/2
• xが奇数の時f(x)=x-1

正整数vに対し、1になるまで繰り返しfを適用した数列[v,f(v),f(f(v)),....,1]を考える。
p(v)をこの数列とする。
正整数N,Kが与えられる。1≦x≦Nの範囲で、p(x)中にyが現れるようなものがK回以上現れるような最大のyを求めよ。

解法

c(v)をp(x)中にvが現れるような回数とする。
c(v)≧c(v+2)なので、vを奇数・偶数それぞれの範囲で二分探索して、c(v)がK以上になる最大値を求めよう。

ll N,K;

ll num(ll v) {
	ll ret=0;
	int i;
	FOR(i,61) {
		if((v<<i)>N) break;
		ll L=v<<i;
		ll R=((v+(v%2==0?2:1))<<i)-1;
		R=min(R,N);
		if(R>=L) ret+=R-L+1;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	ll ma1=1;
	for(i=60;i>=1;i--) if(num(ma1+(1LL<<i))>=K) ma1+=1LL<<i;
	ll ma2=0;
	for(i=60;i>=1;i--) if(num(ma2+(1LL<<i))>=K) ma2+=1LL<<i;
	cout<<max(ma1,ma2)<<endl;
}

まとめ

Eは問題文シンプルなのにね。