ARC 091 F. Strange Nim

atcoder.jp

考察

• 独立なゲームが個あるのでGrundy数を考えてみる。が例えば十分大きい偶数なら以下の様になる

0, ..., K-1 | K, ... , 2K - 1 | 2K, ...
0, 0, ....0 | 1, 0, .... 1, 0 | 2, 1, 0, 2, 1, 0... 

• Grundy数さえ高速に(くらいで)求められればXOR取るだけ
• 愚直に求めようとすると間に合わないので周期性を用いたい
• が大きい場合と小さい場合に分けてそれぞれの特徴を活かして計算するタイプのやつだろうと直感が働く
• まずが大きい場合、上の例で縦棒で区切っているようにK個ごとのグループに分ける。このときが大きければ(具体的には以上とか)グループ数はさほど多くない(程度)。 番目のグループ内では番目のグループの最後の個にを加えた周期の列が繰り返される。この各グループの周期を求めるのは列の切り貼り挿入ができる平衡二分探索木を用いればlog一つくらい乗るがシミュレーションできる。
• 次にが小さい場合について考えるものの、グループ数が多すぎて手に負えず困った。
• ここで断念して解説を見た

想定解

• Grundy数をと書くことにするとがの倍数でないとき、倍数の時が成り立つ。これは上の考察を踏まえれば簡単にわかる。
• 基本的にはこの式にそって再帰的にもとめていく。ここで前者の場合に、を引いてもなおで割った商が変化しないのであれば一気に引けるだけ引く。これは二分探索で境界を探せば簡単にできる。
• くらいで再帰回数が抑えられ(再帰1回で1ブロック分進むから)、1ステップでだいたい倍くらいになる。
• が大きいときは前者が効いてきて、小さい時は後者が効いてくることでどちらの場合も程度でGrundy数を求められる。

反省点

• Grundy数の様子は把握できていたのにの式を立てられていなかった。周期が見えているときはそれに頼るだけでなくちゃんと定式化するべきだった。(これができていれば大きい場合はわかっていたので、が小さい場合は愚直に再帰して間に合う、ARMERIAさんの解法がそれ(ARC091 F - Strange Nim - ARMERIA))

Submission

int grundy(int a, int k) {
  if (k == 1) return a;
  if (a < k) return 0;
  if (a % k == 0) return a / k;
  int b = a / k;
  int l = 1, r = a / (b + 1) + 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if ((a - (ll)(b + 1) * mid) / k < b)
      r = mid;
    else
      l = mid;
  }
  assert(a - (ll)(b + 1) * l >= 0);
  return grundy(a - (b + 1) * l, k);
}
 
void solve() {
  int n;
  cin >> n;
  int g = 0;
  for (int i = 0; i < n; i++) {
    int a, k;
    cin >> a >> k;
    g ^= grundy(a, k);
  }
  if (g == 0)
    cout << "Aoki" << endl;
  else
    cout << "Takahashi" << endl;
  return;
}