Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2216-4c9fba34
この記事にトラックバックする(FC2ブログユーザー)

January 2012 Cook-Off 5問目 - Zeta-Nim Game (この記事を編集する[管理者用])

Source

codechef January 2012 Cook-Off 4問目
Problem Statement

問題概要

2人でゲームをする.行動できなくなったら負け.先手必勝かごて必勝か判定する問題.
石のN個 (50以下) の山がある.
各山の石の数が与えられる.(2012以下)
最初,各山には,同じ正整数Kが設定されている.
各ターン,各プレイヤーは以下の行動をする.
 1つの山を選び,1個以上,その山に設定されている数字以下の石を取り除く.
 その山に設定されている数字は,そのとき取り除いた石の数に設定し直す.

解法

grundy numberを計算する.
(石の数, 設定された数字) がゲームの状態で,遷移する方法が設定された数字の数だけあるので,愚直に計算するとO(2012^3)かかってしまう.
しかし,(a, b)から遷移できる場所は(a, b-1)から遷移できる場所+1箇所しかないので,(a, b-1)の結果を使いまわすことでそれぞれの状態に対するgrundy numberはO(1)で計算できる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int grundy[2100][2100];

int main(){
  int i,j,k,l,m,n,res;
  int size;
  int a[60], g;

  rep(n,2100){
    rep(i,60) a[i] = 0;
    g = 0;
    REP(k,1,n+1){
      j = k; if(n-k < j) j = n-k;
      i = grundy[n-k][j];
      if(i < 60) a[i]++;
      while(a[g]) g++;
      grundy[n][k] = g;
    }
  }

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&k);
    res = 0;
    while(n--){
      scanf("%d",&i);
      j=k; if(j > i) j = i;
      res ^= grundy[i][j];
    }
    if(!res) puts("Zeta"); else puts("Nancy");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2216-4c9fba34
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。