SRM 322 Div1 Medium ExtendedDominoes

問題

2x1セルのドミノが複数あり、各セルには0~9の数字が書かれている。ドミノの右側の数字とその隣のドミノの左側の数字が同じになるようにドミノをつなげていき、ドミノがループをなるようにする（最左のドミノの左セルと最右のドミノの右セルの数字がおなじになるようにする、またドミノは左右ひっくり返しても良い）。配られたドミノをすべて使うようにして、ループを作るとき、生成パターン数をもとめよ。

やりかた

ドミノの半分を1つのノードとして考える。どのドミノもどれか1つのループに属する。ループに属するということは一筆書きができるということなので、ある1つのパターンに着目した時0~9のノードの次数はすべて2である（そのノードから出て行く辺と、入ってくる辺の2つ。オイラー路）。そして各ノードはいくつかのループの中で使われる可能性があるので各ノードの次数は2 x（使われうるループの数）で必ず偶数でなければならない。

あるノードの次数がmであるとき、ノードが入ってきた時に出て行くのにはm-1通りがある。さらに再び入ってきた時にはm-3通りある（さっき出て行ったやつと今入ってきたやつの2通りを除くから）。次はm-5通りというように1つのノードで(m-1)*(m-3)*...*1通りの頂点の選び方がある。これをすべての頂点について掛けあわせればいい。

以下ソース。

using namespace std;
class ExtendedDominoes {
public:
  long long countCycles(vector <string> pieces){
    int N = pieces.size();
    int deg[11] = {0};
    ll ans = 1;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < 2; j++) deg[pieces[i][j] - '0']++;
    for(int i = 0; i < 10; i++){
      if(deg[i] % 2 == 1) return 0;
      for(int j = 1; j < deg[i]; j+= 2) ans *= j;
    }
    return ans;
  }
};

ドミノを左右ひっくり返してもいいということから、出て行く辺と入ってくる辺を区別する必要がない。

各ノードについて出て行く辺を決めさえすれば、入ってくる辺については勝手に決まる。という考え方に至るのがとても難しいと思った。そもそも数字をノードで考えるというのができなかったし。