yukicoder : No.2521 Don't be Same

シンプルな問題設定良いね。
https://yukicoder.me/problems/no/2521

問題

2つの石の山を使う変則Nimのインタラクティブ問題である。
各自の手番では以下のいずれかを取れる。

• 1個以上石のある山から、その範囲で任意個数の石を取り除く
• 2つの山の石の数が正でかつ等しいとき、すべての石を取り除く

初期状態で2つの山の石の数X,Yが与えられる。
先手後手を任意に選べるとき、相手に勝利せよ。

解法

必敗パターンは、少ない方の山の石が奇数で、多い方がそれより1多い場合である。
初期状態でそうなら後手、そうでなければ初手で上記パターンに持ち込もう。

ll X,Y;

void enemy() {
	string s;
	int x,y;
	cin>>s;
	if(s=="A") {
		cin>>x>>y;
		if(x==1) X-=y;
		else Y-=y;
	}
	else if(s=="B") {
		X=Y=0;
	}
	else {
		exit(0);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	if((X+1==Y&&X%2)||(Y+1==X&&Y%2)) {
		cout<<"Second"<<endl;
		enemy();
	}
	else {
		cout<<"First"<<endl;
	}
	while(1) {
		if(X==Y) {
			cout<<"B"<<endl;
			X=Y=0;
		}
		else if(X>Y) {
			if(Y==0) {
				x=X;
			}
			else if(Y%2) {
				x=X-(Y+1);
			}
			else {
				x=X-(Y-1);
			}
			cout<<"A 1 "<<x<<endl;
			X-=x;
		}
		else {
			if(X==0) {
				y=Y;
			}
			else if(X%2) {
				y=Y-(X+1);
			}
			else {
				y=Y-(X-1);
			}
			cout<<"A 2 "<<y<<endl;
			Y-=y;
		}
		enemy();
	}
	
}

まとめ

Nimのアレンジ色々あるけど、なんか機械的に必勝パターンとかGrundy数とか計算できないものかな…。