AtCoder ABC #255 (エイシングプログラミングコンテスト2022) : G - Constrained Nim

前回に引き続きExよりGの方が難しい。
https://atcoder.jp/contests/abc255/tasks/abc255_g

問題

通常のNimに対し、以下の条件が追加された変則Nimを考える。
山の初期状態に対し、勝者は先手後手どちらか。

• 整数対(X[i],Y[i])が与えられる。X[i]個石のある山から、Y[i]個石を取り除くことはできない。

解法

各山に対応するGrundy数を求め、そのxorが0かどうかを判定する、という点では通常のNimと同じである。
n個の石に対するGrundy数g(n)の計算方法が変則的となる。

Sを、0及びX[i]の集合とする。また、h(n)をmax(g(0),...g(n))とする。
Sに含まれないnについては、g(n)=h(n)=h(n-1)+1となる。
なので、Sに含まれるn未満で最大の整数mに対し、g(n)=h(n)=(n-m)+h(m)となる。
よって、m∈Sに対するg(m)・h(m)さえ求めておけば、それ以外のnに対するg(n)・h(n)も求められることになる。

あとは、m∈Sに対し小さい順にg(m)・h(m)を求めよう。
{g(0),g(1),.....g(m-1)}を考えると、0以上h(m-1)以下の値がほとんど1個で、稀にm'∈S (m'＜m)に対しg(m')が複数個あることになる。
そこで、{g(0),g(1),.....g(m-1)}のうち2個以上含まれる値だけ記録しておこう。
そこから、X[i]=mであるようなY[i]に対し、g(m-Y[i])を取り除いた時、登場回数が0回となる最小値を求めれば、それがg(m)となる。

int N,M;
ll A[202020];
ll X[202020],Y[202020];
map<ll,vector<ll>> NG;
map<ll,ll> G,H;

ll getG(ll n) {
	if(G.count(n)) return G[n];
	auto it=H.lower_bound(n);
	it--;
	ll n2=it->first;
	return n-it->first+it->second;
}
ll getH(ll n) {
	if(H.count(n)) return H[n];
	auto it=H.lower_bound(n);
	it--;
	ll n2=it->first;
	return n-it->first+it->second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		NG[X[i]].push_back(Y[i]);
	}
	NG[0].clear();
	G[0]=H[0]=0;
	map<ll,int> cnt;
	FORR2(a,b,NG) if(a) {
		ll cand=getH(a-1)+1;
		ll emp=cand;
		map<ll,int> rem;
		FORR(c,b) {
			ll g=getG(a-c);
			if(rem.count(g)) {
				rem[g]--;
			}
			else if(cnt.count(g)) {
				rem[g]=cnt[g];
			}
			else {
				rem[g]=0;
			}
			if(rem[g]==0) emp=min(emp,g);
		}
		G[a]=emp;
		H[a]=max(getH(a-1),G[a]);
		if(cand!=emp) cnt[emp]++;
		
	}
	
	
	ll gr=0;
	FOR(i,N) gr^=getG(A[i]);
	if(gr) {
		cout<<"Takahashi"<<endl;
	}
	else {
		cout<<"Aoki"<<endl;
	}
	
}

まとめ

なるほど…。