ARC091 F - Strange Nim

問題ページ
F - Strange Nim

考えたこと

• 明らかにgrundy数の見た目をしてるので実験
• 石の数がk個未満になったら操作不可能なのでgrundy数を0とする
• いろいろ実験していると a%k=0ならgrundy数がa/kになることに気づく
• さらに実験していると 石の数a個のgrundy数 = 石の数(a-floor(a/k)-1)個のgrundy数 になりそう
• a%k=0になるまで a=a-a/k-1 と更新し続けるのを書く
• sampleが通ったので出すとTLE
• よくよく考えるとkが大きい時に更新回数がとんでもないことになる
• floor(a/k)が切り替わるまではまとめて計算していいのでは？
• まとめて計算することにして出すと通る

自力で通せたけど1時間以上かかっているためコンテスト中には不可能だった
もうちょっと実験から気づく速度を上げたい

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  ll tot = 0;
  REP(i, n) {
    int a, k;
    cin >> a >> k;
    while(a%k && a >= 2*k) {
      int cost = a/k + 1;
      int dif = a-a/k*k;
      a -= ceil(dif,cost)*cost;
    }
    if(a >= 2*k) tot ^= a/k;
    else if(a >= k) {
      tot ^= !((a-k)%2);
    } else {
      tot ^= 0;
    }
  }

  if(tot) cout << "Takahashi" << endl;
  else cout << "Aoki" << endl;

  return 0;
}