KUPC2015 : H - Bit Count

これは本番解けた。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_h

問題

正整数Nが与えられる。
NとN+Xのbitcountが一致するような正整数Xの最小値のを求めよ。

解法

Xの(2進数表記での)上のbitから順に0,1を決めていく。

今Xの下からD bit目を考えるとする。
Xが上から(D+1)桁目までは決まっているなら、(N+X)も上から(D+1)桁目までは決まっていることになる。
仮に、(D+1)桁目から上にp個1が並んでいるとする。
もし(N+X)のD桁目が繰り上がる場合、上にあるp個の1は消え、(D+p+1)桁目に1が1個できる。
すなわち繰り上がるとp-1個1が減少する。
言い換えると、直前の桁に何個1が連続しているか、を状態として持っておくと繰り上がりの影響がわかる。

以下のコードでは、dfs(桁, 上の桁にある連続した1の数, ここまで登場した1の数, leading zeroの有無)を状態としてメモ化再帰した。
Xの最小値を求めたいので、そのbitを0にして条件を満たせるならそちらを取り、無理なら1を取る、として上のbitから決めていけば良い。

int T;
ll N;
ll memo[65][65][140][2];

ll dfs(int d,int mi,int dif,int lz) {
	if(d==-1) {
		if(lz==0) return -2;
		if(dif==0) return 0;
		else return -2;
	}
	ll& ret=memo[d][mi][dif+70][lz];
	if(ret==-1) {
		
		if(N&(1LL<<d)) {
			// take zero
			ret=dfs(d-1,mi+1,dif+1,lz);
			if(ret<0) {
				ret=dfs(d-1,0,dif-mi,1);
				if(ret>=0) ret+= 1LL<<d;
			}
		}
		else {
			// take zero
			ret=dfs(d-1,0,dif,lz);
			if(ret<0) {
				ret=dfs(d-1,mi+1,dif,1);
				if(ret>=0) ret+= 1LL<<d;
			}
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T;
	while(T--) {
		cin>>N;
		MINUS(memo);
		cout<<dfs(60,0,0,0)<<endl;
	}
}

まとめ

本番だいぶ状態遷移が頭の中で混乱したけど、最終的に解けて良かった。