AtCoder ARC #091 : F - Strange Nim

今回実験ゲー成分強いな。
https://beta.atcoder.jp/contests/arc091/tasks/arc091_d

問題

N個の山があり、各山iは石がA[i]個とパラメータK[i]が設定されている。
これを用いて２人でNimを行う。

ただし通常のNimと異なり、山から取り除ける石の数の上限はその時点の石の数をXとするとfloor(X/K[i])個である。
２人が最適手を取ると、先手後手勝者はどちらか。

解法

Nimの定番としてGrundy数のxorを求めよう。
f(A,K) := パラメータK、石の数Aの山におけるGrundy数

問題はf(A,K)の求め方である。
試しに小さい数で試すと、以下のことがわかる。

• A＜Kならf(A,K)=0
• AがKの倍数ならf(A,K)=A/K
• 上記以外の場合、f(A,K)=f(A-ceil(A/K),K)

基本的には上記処理に則り再帰的にf(A,K)を求める。
Kが大きくceil(A/K)が小さいと３つ目の式は再帰の回数が増えるので、A/Kが変化しない範囲でceil(A/K)はまとめて何回分も引いてしまおう。

int N;
int A,K;
int gr[101010];

int hoge(int A,int K) {
	if(A<K) return 0;
	if(A%K==0) return A/K;
	
	int dif=((A/K)+1);
	return hoge(A-max((A%K)/dif,1)*dif,K);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	/*
	for(i=0;i<=100;i++) {
		set<int> S;
		for(x=1;x<=i/N;x++) S.insert(gr[i-x]);
		while(S.count(gr[i])) gr[i]++;
		cout<<i<<" "<<gr[i]<<" "<<hoge(i,N)<<endl;
	}
	
	return;
	*/
	int nim=0;
	FOR(i,N) {
		cin>>A>>K;
		nim ^= hoge(A,K);
	}
	if(nim==0) cout<<"Aoki"<<endl;
	else cout<<"Takahashi"<<endl;
}

まとめ

これ想定解なのかな…。