Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM561 DIV1 MEDIUM - CirclesGame (この記事を編集する[管理者用])

Source

TopCoder SRM561 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

2次元平面上にn個 (50以下) の円が与えられる.
各円周は重なっていないが,ある円が別の円を包含しているかもしれない.
2人でゲームを行う.順番に行動して,行動できなくなったら負け.先手必勝か後手必勝かを判定する問題.
各ターンは以下の行動をする.
 内部に赤い点がない円を1つ選んで,その円の中の好きな(ただし他の円の円周は選ばない)1点を赤くする.

解法

Grundy数を計算する.
円をノードとみなして,中にある円(のうち,中にある円の中でないもの)を子供とみなして森を作る.
ある場所を赤い点で塗ると,該当するノードとその親,その親,…,その木のルートがなくなって,新しい木がいくつかできるような感じになる.
各ノードをルートとみなした時の部分木のGrundy数を全部計算すれば良い.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int dist2(int dx, int dy){ return dx*dx+dy*dy; }

int n, edge[55][55], up[55];

int memo[1000];
int solve(int r){
  int i, j, k;
  int cur, bef, val;
  int arr[200];

  if(memo[r] >= 0) return memo[r];
  rep(i,200) arr[i] = 0;

  rep(k,n) if(k==r || edge[r][k]){
    val = 0;
    cur = k; bef = -1;
    for(;;){
      rep(i,n) if(up[i]==cur && i!=bef) val ^= solve(i);
      if(cur==r) break;
      bef = cur;
      cur = up[cur];
    }
    if(val < 200) arr[val] = 1;
  }

  rep(i,200) if(!arr[i]) break;
  return memo[r] = i;
}

class CirclesGame {
public:
string whoCanWin(vector <int> x, vector <int> y, vector <int> r) {
  int i, j, k;
  int res = 0;

  n = x.size();
  rep(i,n) rep(j,n) edge[i][j] = 0;

  rep(i,n) rep(j,n) if(i!=j){
    if(dist2(x[i]-x[j],y[i]-y[j]) < r[i]*r[i] && r[i] > r[j]) edge[i][j] = 1;
  }

  rep(i,n) up[i] = -1;
  rep(i,n){
    rep(j,n) if(edge[j][i]){
      rep(k,n) if(edge[j][k] && edge[k][i]) break;
      if(k==n) up[i] = j;
    }
  }

  rep(i,n) memo[i] = -1;
  rep(i,n) if(up[i]==-1) res ^= solve(i);

  if(res) return "Alice";
  return "Bob";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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