TopCoderOpen 2016 Round1C Hard PrimeStrings

最近桁DPにだいぶ飽きてきた(解けるとは言っていない)。
https://community.topcoder.com/stat?c=problem_statement&pm=14015

問題

正整数Aにf(A)を以下のように定義する。
B(A)をAの二進数表記とする。
f(A)は、B(A)のうちmax(|B(A)|-k,1)桁だけ残してできる(leading zeroを含まない)二進数のうち最大値とする。

x,y,kが与えられる。
i=1～xのうち、f(i)≦yとなるiの数を求めよ。

解法

大半のiは２進数表記の桁数だけで判定できる。

• |B(i)|-k ＜ |B(y)| となるようなiは条件を満たす。
• |B(i)|-k ＞ |B(y)| となるようなiは条件を満たさない。

よって、|B(i)|-k == |B(y)|となるような桁数のiについてだけ詳細に見ていこう。
以下|B(x)|-k == |B(y)|のケースを考える。

B(x)

-k ＜

B(y)

だったら

B(i)

-k ==

B(y)

となるiはxを超えるため答えの対象外だし、

B(x)

-k ＞

B(y)

であればx = 2^(B(y)+k-1)-1 ((B(y)+k)桁の２進数の最大値)として扱えばよい。

上の桁から桁DPの要領で、k桁を除き0か1を選択していく。
途中xを超えてしまうような0,1は取れない。
また、f(A)は最大値を取ろうとするので、除くk桁は積極的に0を取り除く。
0を残すのは、残り桁全部選択しないといけない場合だけである。
このようにして、y以下となる選び方を列挙していく。

class PrimeStrings {
	public:
	map<pair<ll,ll>,ll> M[60][60];
	
	ll dp(ll x,ll y,int bx,int by) {
		if(by<0) return (x+1);
		if(M[bx][by].count({x,y})) return M[bx][by][{x,y}];
		
		ll ret=0;
		
		if(bx==by) {
			if(y&(1LL<<by)) {
				if(x&(1LL<<bx)) ret = dp(x^(1LL<<bx),y^(1LL<<by),bx-1,by-1) + (1LL<<bx);
				else ret = x+1;
			}
			else {
				if(x&(1LL<<bx)) ret = dp((1LL<<bx)-1,y,bx-1,by-1);
				else ret = dp(x,y,bx-1,by-1);
			}
		}
		else {
			if(y&(1LL<<by)) {
				if(x&(1LL<<bx)) ret = dp(x^(1LL<<bx),y^(1LL<<by),bx-1,by-1) + dp((1LL<<bx)-1,y,bx-1,by);
				else ret += dp(x,y,bx-1,by);   // take0
			}
			else {
				if(x&(1LL<<bx)) ret += dp((1LL<<bx)-1,y,bx-1,by);   // take0
				else ret += dp(x,y,bx-1,by);   // take0
			}
		}
		M[bx][by][{x,y}] = ret;
		return ret;
	}
	
	long long getCount(long long x, long long y, int k) {
		int bx=0,by=0;
		while((1LL<<bx)<=x) bx++;
		while((1LL<<by)<=y) by++;
		ll ret=0;
		int i,j;
		FOR(i,60) FOR(j,60) M[i][j].clear();
		for(i=1;i<=bx;i++) {
			int t=i-k;
			if(t<by) ret+=min((1LL<<i)-1,x)-((1LL<<(i-1))-1);
			if(t==by) {
				if(i==bx) ret+=dp(x^(1LL<<(bx-1)),y^(1LL<<(by-1)),bx-2,by-2);
				else ret+=dp((1LL<<(i-1))-1,y^(1LL<<(by-1)),i-2,by-2);
			}
		}
		
		return ret;
	}
}

まとめ

桁DP系は上か下から順にやっていくばかりで、手間ばかり面倒で面白さが感じられないので余り好きじゃない。
面白い桁DPないかな…。