CODE FESTIVAL 2016 Relay : F - 3分割ゲーム / Trichotomy

途中で用事でやめちゃったけど、最後までやればもう少し行けたかも。
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_f

問題

整数Kに対し、Nが３以上であれば３つの正整数に分割し、中間値を残す、という処理を繰り返す。
この処理を最大X回行えるようなNの最大値を求めよ。

解法

二分探索で解く。
中間値をできるだけ大きくしたいので、以下のように分割し、X回分割できるか判定すればよい。

• Nが奇数なら1,(N-1)/2,(N-1)/2
• Nが偶数なら1,N/2-1,N/2

int X;

int ng(ll v) {
	int i;
	FOR(i,X) {
		if(v%2) v=v/2;
		else v=(v-1)/2;
	}
	if(v>2) return 1;
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>X;
	ll A=(1LL<<60)-1;
	for(i=59;i>=0;i--) if(ng(A-(1LL<<i))) A-=1LL<<i;
	cout<<(A-1)<<endl;
	
}

まとめ

まぁこれはすんなり。