yukicoder No.669 対決!!! 飲み比べ

問題ページ
No.669 対決!!! 飲み比べ - yukicoder

考えたこと

• 取れる石の数の上限がK個のNim
• grundy数を使えという雰囲気を感じる
• 実験をすると「0 1 2 3 … k 0 1 2 3 … k …」みたいな周期になる
• つまり a[i]%(k+1) でそれぞれの山のgrundy数が求まる
• あとはいつもどおりXORを取って0かそれ以外か見る

grundy数の入門にちょうどいい問題な気がした

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

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

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

  int n, k;
  cin >> n >> k;
  VI a(n);
  REP(i, n) cin >> a[i];

  int tot = 0;
  REP(i, n) tot ^= a[i]%(k+1);
  
  if(tot==0) cout << "NO" << endl;
  else cout << "YES" << endl;

  return 0;
}