ARC091 F : Strange Nim(900)
作成日：2018.03.14
最終更新日：2018.03.14
問題概要
山が$N$個あり、$i$番目の山には$A_i$個の石がある。
2人が交互に操作「$i$個目の山を選び、$1$個以上$X/K_i$個以下の個数の石をその山から取り除く」を行う。
先に操作を行えなくなった方が負けである時、先手と後手のいずれに必勝手順があるかを判定せよ。
制約
$1 \leq N \leq 200$
$1 \leq A_i , K_i \leq 10^9$
考え方
二人で交互に同じ操作を行うゲームなので、Grundy数を考える。
各山は独立しているから、山ごとにGrundy数を求めて、それらのxorをとれば良い。
すなわち、1つの山のGrundy数が求められれば良い。
石が$a$個ある時のGrundy数を$g_a$とする。
例えば$K=3$とすると、$g_0,g_1,...$は$0$,$0$,$0$,$1$,$0$,$1$,$2$,$0$,$1$,$3$,$2$,$0$,$4,...$となる。
$[a/K] = m$の時、$g_a$は$g_{a-1},...,g_{a-m}$に含まれない最大の非負整数である。
このことから$g_a \leq m$であり、周期が$m+1$であることが分かる。
さらに$m$の値が増える時、すなわち$a$が$K$の倍数の時、$g_a = a/K$となることも分かる。
以上のことを用いると$g_a$が$K$の倍数か$K$未満の時は$O(1)$で求まるが、そうでない時は$g_a = g_{a-[a/K]-1}$を繰り返し適用する必要がある。
この計算量は$[a/K]$の値ごとに行う引き算の回数を考えると$K \sum_{i \leq [A/K]}(1/i)$であるから、$O(A \: log(A/K))$であることが分かる。
これでは間に合わないので工夫する。
計算量を求めた時に$[a/K]$の値ごとにまとめたが、引き算もその値ごとにまとめることができる。
すなわち$t([a/K]+1)$が$a\%K$以上になる最小の$t$だけまとめられる。
この$t$は$(a\%K)/([a/K]+1)$である。
引き算は高々$A/K$回であり、$A/K \geq K$の時には$A-A/K$$=A(K-1)/K$であるから指数関数的に$A$が減少していく。
よって計算量は$O(min(A/K,$$K \: log \: A))$$\leq O(\sqrt K \: log \: A)$であるから十分高速である。
ソースコード
マクロ等はこちら
int N;
int solve(int a , int k){
if(a<k) return 0;
if(a%k==0) return a/k;
int d = a/k + 1;
d = (a%k+d-1)/d*d;
return solve(a-d,k);
}
int main(){
cin >> N;
int g = 0;
repp(i,0,N){
int A,K;
cin >> A >> K;
g ^= solve(A,K);
}
cout << (g==0?"Aoki":"Takahashi") << endl;
return 0;
}解法まとめ
$A,K$の組ごとにGrundy数を求め、それらのxorが$0$なら後手、そうでないなら先手が勝つ。(13-19行)
$A,K$が与えられた時のGrundy数は、$A \lt K$の時$0$、$A$が$K$の倍数の時$A/K$、いずれでもない時は$A$を$A-A/K-1$に置き換えたものに等しい。
ここで$A/K$が変わらない部分はまとめて計算する。
具体的には$\lceil (A\%K)/([A/K]+1) \rceil$回分をまとめることができる。(3-9行)