yukicoder : No.3554 Rurumaru Function Problem 2

なるほど…。
https://yukicoder.me/problems/no/3554

問題

f(x,y)を２進数表記したときの2^iの桁は、

• iが偶数の場合、xとyの2^i桁目のAND
• iが奇数の場合、xとyの2^i桁目のOR

とする。

g(n)を、0≦x,y＜nの範囲で取ったときのf(x,y)の最頻値の最小値とする。

正整数Nが与えられるので、を答えよ。

解法

h(n,v)を、f(x,y)=vとなるn未満のx,yの個数とする。
g(n)を探索すると、以下の特徴がある。

• g(n)は単調増加
• g(n)は4進数表記で2を並べた値しかとらない

よってg(0)＝g(N)は高々O(logN)通りの値しかとらないので、二分探索で値が切り替わるポイントを求めよう。

4進数表記で2をi個並べた値をF(i)とすると、h(n,F(i))がわかればこの二分探索が出来、これは桁DPで求められる。

ll U[31];
ll M,V;
ll memo[31][2][2];

ll dfs(int d,int le1,int le2) { // 確定したビットと、M未満が確定したかどうか
	if(d==-1) return 1;
	if(memo[d][le1][le2]>=0) return memo[d][le1][le2];
	ll ret=0;
	ll mb=(M>>d)%2;
	ll vb=(V>>d)%2;
	int x,y;
	FOR(x,2) FOR(y,2) {
		if(le1==0&&x>mb) continue;
		if(le2==0&&y>mb) continue;
		if(d%2) {
			if((x|y)==vb) ret+=dfs(d-1,le1|(x<mb),le2|(y<mb));
		}
		else {
			if((x&y)==vb) ret+=dfs(d-1,le1|(x<mb),le2|(y<mb));
		}
	}
	return memo[d][le1][le2]=ret;
	
}

ll H(ll n,ll v) {
	// f(x,y)=vとなるn未満のx,yの個数
	if(n==0) return 0;
	
	MINUS(memo);
	M=n-1;
	V=v;
	return dfs(30,0,0);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,30) U[i+1]=U[i]*4+2;
	int N;
	cin>>N;
	ll ret=0;
	ll pre=0;
	FOR(i,30) {
		ll L=pre,R=N+1;
		while(R-L>1) {
			ll M=(R+L)/2;
			if(H(M,U[i])>=H(M,U[i+1])) {
				L=M;
			}
			else {
				R=M;
			}
		}
		ret+=(R-pre)*U[i];
		pre=R;
	}
	cout<<ret<<endl;
}

まとめ

最初にg(n)の特性を思いつくまでの敷板が高いな…実験した方が速いかもだけど。