SnackDown Online Qualifier 2016 - Floor Division Game

問題

https://www.codechef.com/SNCKQL16/problems/FDIVGAME

解法

grundy 数に規則性がある (のを uwi さんに教えてもらった) ので、それを先に作っておいて、参照しながら求めると良い。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  // 先に grundy 数の map を作っておく
  map<int64_t, int> nim;
  nim[0] = 0;
  nim[1] = 1;
  nim[2] = 2;
  nim[4] = 3;
  int p = 3;
  while (nim.rbegin()->first < 1e18) {
    int64_t n = nim.rbegin()->first;
    if (nim.size() % 4 == 0) {
      n += n / 2;
    } else {
      n *= 2;
    }
    nim[n] = (++p) % 4;
  }


  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    vector<int64_t> A(N);
    for (int i = 0; i < N; ++i) {
      cin >> A[i];
    }

    vector<int> G(N);
    for (int i = 0; i < N; ++i) {
      auto it = nim.upper_bound(A[i]);
      it--;
      G[i] = it->second;
    }

    int grundy = 0;
    for (int i = 0; i < N; ++i) grundy = grundy ^ G[i];
 
    if (grundy > 0)
      cout << "Henry" << endl;
    else
      cout << "Derek" << endl;
  }
}