Codeforces #633 Div1 C. Perfect Triples

これは実験ゲーかな。
https://codeforces.com/contest/1338/problem/C

問題

以下のように構成される数列sを考える。
初期状態でsは空である。

• 正整数の組(a,b,c)のうち、以下を満たすもので辞書順最小のものを見つけ、sの末尾にa,b,cとして加える
  • a,b,cはいずれもsに含まれない
  • a xor b xor c = 0

sのN要素目の値を求めよ。

解法

実験してみると、1～(4^n-1)のあと、(4^n)～(4^(n+1)-1)が似たような形状で再帰的な構造を成して並ぶことがわかる。
なので同様に再帰関数を作って求めて行くとよい。

int T;
ll N;

ll hoge(ll v) {
	ll ret;
	if(v%4==0) ret=0;
	if(v%4==1) ret=2;
	if(v%4==2) ret=3;
	if(v%4==3) ret=1;
	
	if(v>=4) ret=hoge(v/4)*4+ret;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	set<int> S;
	/*
	x=1;
	FOR(i,30) {
		while(S.count(x)) x++;
		for(y=x+1;;y++) {
			if(S.count(y)) continue;
			if(S.count(x^y)) continue;
			break;
		}
		
		cout<<x<<" "<<y<<" "<<(x^y)<<endl;
		S.insert(x);
		S.insert(y);
		S.insert(x^y);
	}
	*/
	
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll P=(N-1)/3;
		ll Q=(N-1)%3;
		
		for(i=0;;i+=2) {
			if(P<1LL<<i) break;
			P-=(1LL<<i);
		}
		int step=i;
		ll X=1LL<<step;
		ll Y=1LL<<(step+1);
		
		ll a=X+P;
		ll b=Y+hoge(P);
		ll c=a^b;
		
		if(Q==0) cout<<a<<endl;
		if(Q==1) cout<<b<<endl;
		if(Q==2) cout<<c<<endl;
		
		
	}
}

まとめ

こういう実験ゲー、なかなかサクサク解けないんだよな。