3668 - A Funny Stone Game

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=1669
Regionals 2006 :: Asia - Beijing
I問題

問題

２人で行うゲームを考える。
0〜n-1の番号がついたn個の石の山があり、それぞれの山に何個かの石が積まれている。
プレイヤーは自分の番に３つの数 i, j, k (i < j, j <= k, 山iには1つ以上の石が残っている)を決める。
その後、山iから石を１つ取り、山j,kそれぞれに石を１つずつ追加する。
これを２人が繰り返し、先にi,j,kを選べなくなったほうが負けとなる。
それぞれの山の石の数の初期値が与えられるので、先手が勝てるかどうか判定せよ。
勝てる場合、どのようなi,j,kを選べばいいのかも求めよ。
ただし複数ある場合は辞書順最小を求めるものとする。

制約

1<=n<=23
0<=石の数の初期値<=1000

解法

Grundy数。
蟻本のゲームの章の最後に載っている、分裂が起きるタイプのGrundy数が参考になる。
今、山iにある石１つに注目すると、この石の状態はn-iで表すことが出来る。
状態n-iから１回の操作で、状態n-jと状態n-kに分裂すると考えることが出来、蟻本と同様に状態n-iのGrundy数を求めることが出来る。
全体の勝敗判定をする場合は、全ての石についてのGrundy数をXORすれば出来る。
ただし、ある山の石についてXORするときは、XORの性質から石の数の偶奇で場合分けするだけでよい。
それにしてもGrundy数は狐に抓まれたような気持ちになる・・・・

ソース

int g[50];
 
int grundy(int x) {
  if (g[x] >= 0) return g[x];
  set<int> s;
  REP(i,x) {
    REP(j,i+1) {
      s.insert(grundy(i) ^ grundy(j));
    }
  }
  int res = 0;
  while(s.count(res)) ++res;
  return g[x] = res;
}
 
int a[50];
 
int main() {
  REP(i,50) g[i]=-1;
  REP(i,50) grundy(i);
  int n;
  int cs = 1;
  while(cin>>n,n) {
    printf("Game %d: ", cs++);
    REP(i,n) cin >> a[i];
    int now = 0;
    REP(i,n) if (a[i]&1) now ^= g[n-i-1];
    if (now == 0) puts("-1 -1 -1");
    else {
      REP(i,n-1) {
        if (a[i] == 0) continue;
        for (int j=i+1; j<n; ++j) {
          for (int k=j; k<n; ++k) {
            if ((now ^ g[n-i-1] ^ g[n-j-1] ^ g[n-k-1]) == 0) {
              printf("%d %d %d\n", i,j,k);
              goto next;
            }
          }
        }
      }
    next:;
    }
  }
}