SRM 495 Div2 Hard HexagonPuzzle

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11303&rd=14424

正六角形を組み合わせた三角の形をしたタイルがある。このうちのいくつかの正六角形はlocked、死んだ状態にあり、それ以外の正六角形は各々ことなる色で塗られている。同じ頂点を共有するlockedされていない3つのタイルはその色を半時計回りに動かすことができる。全部で何通りのタイルの塗り方があるか。

やりかた

practice roomの[ [iwi] ]さんの解答を参考にしました。

すべての正六角形間で色の交換が行えるようなひとつの領域があるとして、その領域がn個の正六角形からなるとき、その領域の色の塗り方の総数は。（n個の正六角形の塗り方n!中、2つの正六角形のみが交換されているという状況をどうやってもつくることはできない。という説明でいいのか。。。）これを互いに色を交換できるグループごとに計算してかけあわせればいい。

グループを求めた後に、そのグループの領域の大きさを計算する。それには単純に幅優先探索などであるものいいけど、union-findでひとまず領域ごとにまとめた後、領域の数を求めるという方法が賢い。

int par[10000], rrank[10000];

void uf_init(int n){
  for(int i = 0; i < n; i++){
    par[i] = i;
    rrank[i] = 0;
  }
}

int uf_find(int x){
  return (par[x] == x) ? x : par[x] = uf_find(par[x]);
}

void uf_unite(int x, int y){
  x = uf_find(x);
  y = uf_find(y);
  if(x == y) return;
  if(rrank[x] < rrank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rrank[x] == rrank[y]) rrank[x]++;
  }
}

class HexagonPuzzle {
public: 
  int theCount(vector <string> board) {
    int N = board.size();
    ll MOD = 1000000007;

    int id[60][60];
    int l = 0;
    for(int i = 0; i < N; i++) for(int j = 0; j <= i; j++) id[i][j] = l++;

    uf_init(l);
    for(int i = 0; i < N - 1; i++){
      for(int j = 0; j < i; j++){
	if(board[i][j] == '.' && board[i][j + 1] == '.' && board[i + 1][j + 1] == '.'){
	  uf_unite(id[i][j], id[i][j + 1]);
	  uf_unite(id[i][j], id[i + 1][j + 1]);
	}
      }
      for(int j = 0; j <= i; j++){
	if(board[i][j] == '.' && board[i + 1][j] == '.' && board[i + 1][j + 1] == '.'){
	  uf_unite(id[i][j], id[i + 1][j]);
	  uf_unite(id[i][j], id[i + 1][j + 1]);
	}
      }
    }

    ll ans = 1;
    for(int i = 0; i < N; i++){
      for(int j = 0; j <= i; j++){
	int c = 0;
	for(int ti = 0; ti < N; ti++) 
	  for(int tj = 0; tj <= ti; tj++)
	    if(uf_find(id[ti][tj]) == id[i][j]) c++;
	if(c >= 3) 
	  for(int a = 3; a <= c; a++) ans = (ans * a) % MOD;
      }
    }
    return ans;
  }
};

やりかたはすぐ気づくができたけど領域に分けるところで頭を使わず単なるBFSをしたため、下のケースで

サイズ3の領域が2つとかぞえるべきところをサイズ6の領域が1つと数えてしまってWA。
そうか領域判断しながらすぐにunion-findに突っ込んでいけばいいのかー。
勉強になった(・o・)