AtCoder Regular Contest 091 F - Strange Nim

問題概要

高橋くんと青木くんが Nim (石取りゲーム) をする．ただし先攻は高橋くんで，それぞれの山から1回に取れる石の数に以下のような制約がある．

• $ N $個の山があり，$ i $番目の山は最初$ A_i $個の石がある．
• ある地点で$ i $番目の山にある石の数を$ X_i $個とするとき，その地点では$ i $番目の山から$ {\mathrm floor} (X_i/K_i )$個までの石を取ることができる．

解法概要

それぞれの山に対してgrundy数を求め，grundy数のxorが0なら青木くんの勝ち，0でないなら高橋くんの勝ち． grundy数は実験してみると

• $ X_i = 0, K_i+1 $のとき0
• $ X_i \% K_i = 0 $のとき$ X_i/K_i $
• それ以外のときは山にある石の数が$ X_i - ( {\mathrm floor} (X_i/K_i ) + 1 ) $である場合と等しいgrundy数

であることがわかる (厳密な証明は公式解説参照) ．

ただし愚直に再帰で求めようとすると$ X_i/K_i $が小さく，$ K_i $が非常に大きいような場合にTLEしてしまうので，$ X_i - ( {\mathrm floor} (X_i/K_i ) + 1 ) $のソースコード

#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)

using namespace std;

typedef long long ll;

ll grundy(ll a, ll k){
    if(a % k == 0LL) return a/k;
    if(a == k+1) return 0LL;
    return grundy(a - (a/k+1) * max(1LL, (a%k) / (a/k+1)), k);
}

int main(){
    int n;
    cin >> n;
    ll a,k,g = 0LL;
    rep(n){
        cin >> a >> k;
        g = g ^ grundy(a, k);
    }

    cout << (g?"Takahashi":"Aoki") << endl;
}

感想

高速化部分の理解が私にはちと難しかったが，得意になれそうな分野なので粘ってみた．