Codeforces #931 : Div2 D2. XOR Break — Game Version

D1と問題設定は近いっちゃ近いけども。
https://codeforces.com/contest/1934/problem/D2

問題

正整数を用いて、以下の2人ターン制ゲームを行う。

• 自身のターンが来た時の整数の現在値をpとする。p1 xor p2 かつ、p1もp2もp未満の正整数となるp1,p2を選ぶ。そのようなp1,p2がない場合負け。
• その後、相手がp1,p2のいずれかを選び、現在値とする。

正整数の初期値Nが与えられる。
自身が必勝となるには、先手・後手どちらを取ればよいか。
またその後実際に手番を示せ。

解法

自分のターンはpのbitcountが偶数、相手のターンはbitcountが奇数となるようにしよう。
相手は最終的にpが1 bitしか立たなくなり、p1,p2を選べなくなる。

なので、まずNのbitcountで先手後手を定める。

• 相手の手番では、p1とp2のどちらかのbitcountが偶数なので、自分はそちらを選択する。
• 自分の手番では、pのbitcountが偶数なので、p1もp2もbitcountが奇数となるようにする。

int T;
ll N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		int turn=0;
		if(__builtin_popcountll(N)%2==0) {
			cout<<"first"<<endl;
		}
		else {
			cout<<"second"<<endl;
			turn++;
		}
		
		while(1) {
			if(turn) {
				ll a,b;
				cin>>a>>b;
				if(a==0&&b==0) break;
				if(__builtin_popcountll(a)%2==0) N=a;
				else N=b;
			}
			else {
				ll a=0;
				FOR(i,60) if(N&(1LL<<i)) a=1LL<<i;
				cout<<a<<" "<<N-a<<endl;
			}
			turn^=1;
		}
		
	}
}

まとめ

割と解法はシンプルで、問題としてはいいんだけどな。