Grundy数 その3

前回までにGrundy数についての説明をしました。augusuto04.hatenablog.com
augusuto04.hatenablog.com
長くなったGrundy数の記事も今回でラスト。実際に使ってみます。

実践例

AtCoder Regular Contest 038のC - 茶碗と豆に挑戦します。

#include <iostream>
using namespace std;
static const int NMAX = 100000;

//Cがラベルの番号、Aが豆の数、gはGrundy数
int N, C[NMAX], A[NMAX], g[NMAX];

int main(){
  cin >> N;
  C[0] = A[0] = g[0] = 0;
  int result = 0;
  for(int i = 1; i <= N - 1; i++){
    cin >> C[i] >> A[i];
    g[i] = 0;
    //茶碗iにおけるGrundy数を求める
    while(true){
      bool d = true;
      for(int j = 1; j <= C[i]; j++){
        if(g[i] == g[i - j]){
          g[i]++;
          d = false;
          break;
        }
      }
      if(d == true)
        break;
    }
    //全体のGrundy数を更新する
    for(int j = 0; j < A[i]; j++){
      result = result ^ g[i];
    }
  }
  if(result > 0)
    cout << "First" << endl;
  else
    cout << "Second" << endl;
}

ただし、これではNとAの値が小さい問題しか解けず、他はタイムアウトになってしまうため部分点の80点しかとれません（まぁ初心者の私にとっては80点でも取れれば大きいんですけどねw）。次の部分点を取るにはAの値が大きいときに対応する必要があります。なので、Grundy数の更新の計算量を少なくしました。

//全体のGrundy数を更新する
for(int j = 0; j < A[i]; j++){
  result = result ^ g[i];
}

上のような計算をしていました。しかし、同じ数を繰り返しxorの計算をすることに実はあまり意味がありません。
a xor a = 0
a xor 0 = a
となるため、同じ数を2回計算するときは無視します。すると次のようになります。

//全体のGrundy数を更新する
if(A[i] % 2 == 1){
  result = result ^ g[i];
}

つまり、偶数回(0回も含む)更新するときは値が変わらないため行わない。奇数回更新するときは1回更新することと同じである。この変更を行うことで100点取れました！ただ、満点は104点です。どうやらg[i]の求め方を工夫する必要があるみたいですね。私はまだ出来ていません。そのやり方やコードの改善等あったら教えていただけると有り難いです。