yukicoder : No.2823 PEX (Predecessing Excluded Value) Game

この知識以前もどこかで見た…かなぁ。
https://yukicoder.me/problems/no/2823

問題

整数集合Sが与えられる。
これを用いて2人ターン制の以下のゲームを行う。

S中の整数xを1つ選ぶ。
その際、x未満の正整数のうち、Sに含まれない最大値をx'とする。
(そのようなx'が存在しないxは選べない)

Sからxを取り除き、x'を加えたらターン終了である。
xを自ターンで選べない場合、負けとなる。
両者最適手を取るとき、勝者はどちらか。

解法

A[n] := Sの要素xのうち、x未満の正整数のうちSに含まれないものがn個あるようなものの個数

とする。各ターンで行えるのは、A[n]が正である正整数nと、A[n]以下の正整数pを選び、A[n]をp減らしてA[n-1]をp増やすことである。
このゲームは、Staircase nimと呼ばれ、nが奇数のもののA[n]のxorが0なら後手必勝となる。
よって、Sのうちnが奇数となるもののの個数を数え上げよう。

int N;
vector<pair<ll,ll>> V={{0,0}};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		ll L,R;
		cin>>L>>R;
		if(V.back().second==L-1) {
			V.back().second=R;
		}
		else {
			V.push_back({L,R});
		}
	}
	ll gr=0;
	ll num=0;
	for(i=1;i<V.size();i++) {
		num+=V[i].first-1-V[i-1].second;
		if(num%2) gr^=V[i].second+1-V[i].first;
	}
	if(gr==0) {
		cout<<"Second"<<endl;
	}
	else {
		cout<<"First"<<endl;
	}
	
}

まとめ

Staircase Nim、見たことあったようななかったような。