TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

完全二分木の制約はD2Hの同じ．今度は$1-indexed$で始まっている完全二分木の存在するノード番号が与えられるので，制約を満たすアルファベットの割り当て方の通りを求める．
全てのノードに置いて部分木の大きさを求めておく．あるノードに対して左の子をleftとしてその部分木の大きさを$cntL$，右の子をrightとしてその部分木の大きさを$cntR$とする．既にleft, rightの部分木のアルファベットの割り当て方の通りが求まっていて$cnt1, cnt2$とすると見ているノードが取れる値の集合の分け方に対して，leftとrightのどの組み合わせでも制約を満たすので$cnt1 * cnt2$通りある．ノードが取れる値の集合の分け方というのはノードの部分木のsize$(L+R)$から左の子の選ぶ組み合わせにで求めることができるので最終的にノードの割り当て方の通りは$cnt1 * cnt2 * {}_{cntL + cntR}C_{cntL}$となる．これを再帰的にやる．

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Node {
  int cntL, cntR;
  Node *left, *right;

  Node() {
      cntL = cntR = 0;
      left = right = NULL;
  }
};

set<int> S;
void build(int x, Node *root) {
  root->left = new Node();
  root->right = new Node();

  if(S.find(2 * x) != S.end()) {
      build(2 * x, root->left);
      root->cntL = (root->left->cntL + root->left->cntR + 1);
  }

  if(S.find(2 * x + 1) != S.end()) {
      build(2 * x + 1, root->right);
      root->cntR = (root->right->cntL + root->right->cntR + 1);
  }
}

ll C[2005][2005];
void combination(int size) {
  for (int i = 0; i < size; i++) C[i][0] = 1LL;
  for (int i = 1; i < size; i++) {
      for (int j = 1; j <= i; j++) {
          C[i][j] = (C[i-1][j-1] + C[i-1][j]);
      }
  }
}

ll dfs(Node *node) {
  if(node == NULL) return 1;
  ll n = node->cntL, m = node->cntR;

  ll cnt1 = dfs(node->left);
  ll cnt2 = dfs(node->right);

  return cnt1 * cnt2 * C[n + m][n];
}

class ConstructBST {

    public:

    long long numInputs(vector <int> tree) {
      Node *root = new Node();
      S.clear();

      rep(i, tree.size()) {
          S.insert(tree[i]);
      }
      build(1, root);

      combination(2000);
      return dfs(root);
    }
};

ry0u_ydのblog

SRM319 D1M ConstructBST

TopCoder Statistics - Problem Statement

Code