Topcoder SRM421ラウンド1ディビジョン1TeamManagement

Topcoder Srm 421 Round 1 Division 1 Teammanagement

説明

持ってるn nnプレーヤー、一部のプレーヤーはクラブに忠実であり、一部のプレーヤーはクラブに忠実ではありません。一部のプレイヤーは友達であり、友達間の関係は対称的ですが推移的ではない根なしの木です。各プレイヤーには最大3人の友達がいます。プレーヤーを購入したい場合は、プレーヤーが忠実であるか、プレーヤーの友人が購入されていることを確認する必要があります。クラブが購入したいk kにプレイヤーは、各プレイヤーが購入される確率を見つけます。

1≤k≤n≤501 leq k leq n leq 501≤に≤n≤50

解決

珍しい性質があります：各プレイヤーには最大3人の友達がいます。したがって、次数がr t rtrtルートとして、各ポイントには最大2人の息子がいます。 、

ツリーdpを実行します。作るf x、c n t、t y p f_ {x、cnt、typ}fバツ、cnt、tYp。ためにx xバツサブツリーのルートとして、を選択しますc n t cntcnt各ポイントのプランの数。定義の基礎tおよびptyptYpの値はわずかに変更されています。

• tおよびp = 0 typ = 0tYp=0：変更なし。
• tおよびp = 1 typ = 1tYp=1：x xバツサブツリーの外側のポイントに接続します。
• tおよびp = 2 typ = 2tYp=二：x xバツサブツリーのポイントに接続します。

転送を検討してください。

x xバツリーフノードです、cnt≤1cnt leq 1cnt≤1。

いつc n t = 0 cnt = 0cnt=0時間：tおよびp = 0、1、2 typ = 0、1、2tYp=0、1、二対応する1、1、0 1,1,01、1、0。いつc n t = 1 cnt = 1cnt=1時間：x xバツ忠実な人のために十一1、x xバツ不誠実な場合：tおよびp = 0、1、2 typ = 0、1、2tYp=0、1、二対応する0、1、0 0、1,00、1、0。

x xバツ非リーフノードであり、x xバツ2人の息子がいるy 1 y_1Y1。とy 2 y_2Y二。。

• 選択しないx xバツ。

  
  
  

  場合y 1 y_1Y1。ルートサブツリーに選択私は私私ポイント、次にy 2 y_2Y二。ルートのサブツリーを選択する必要がありますc n t – i cnt – icnt-私ポイント。乗算の原理によるとf y 1、i、0×f y 2、c n t − i、0 f_ {y_1、i、0} times f_ {y_2、cnt-i、0}fY1。、私、0。××fY二。、cnt-私、0。。正しいi∈[0、c n t] i in [0、cnt]私∈[0、cnt]答えは要約されています。

• 選択x xバツ。

  • tおよびp = 1 typ = 1tYp=1またはx xバツ忠実です。ためにy 1 y_1Y1。とy 2 y_2Y二。それらは、特定のサブツリーの外側のポイントに接続されています（x xバツ）、だから答えはf y 1、i、1×f y 2、c n t − i − 1、1 f_ {y_1、i、1} times f_ {y_2、cnt-i-1,1}fY1。、私、1。××fY二。、cnt-私-1、1。和。

  • t yp≠1typ not = 1tYp。=1そしてx xバツ忠実ではありません。選びたいx xバツ、させなければならないx xバツポイントに接続されているので、y 1 y_1Y1。またはy 2 y_2Y二。の少なくとも1つtおよびp = 2 typ = 2tYp=二。答えは次のようです。fy 1、i、2×fy 2、cnt − i − 1、1 + fy 1、i、1×fy 2、cnt − i − 1、2 f_ {y_1、i、2} times f_ {y_2、cnt -i-1,1} + f_ {y_1、i、1} times f_ {y_2、cnt-i-1,2}fY1。、私、二。××fY二。、cnt-私-1、1。+fY1。、私、1。××fY二。、cnt-私-1、二。。だがtおよびp = 2 typ = 2tYp=二答えはy 1 y_1Y1。とy 2 y_2Y二。両方のサブツリーの忠誠ノードは繰り返しカウントされるため、答えは次のとおりです。fy 1、i、2×fy 2、cnt − i − 1、1 + fy 1、i、1×fy 2、cnt − i − 1、2 − fy 1、i、2×fy 2、cnt − i − 1、2 f_ {y_1、i、2} times f_ {y_2、cnt-i-1,1} + f_ {y_1、i、1} times f_ {y_2、cnt-i-1,2} -f_ {y_1、i、2} times f_ {y_2、cnt-i-1,2}fY1。、私、二。××fY二。、cnt-私-1、1。+fY1。、私、1。××fY二。、cnt-私-1、二。-fY1。、私、二。××fY二。、cnt-私-1、二。。

確率の計算方法については。ポイントの選択を禁止したり、プランの数を見つけたり、使用したりできます1-1-1-禁止されているプログラムと禁止されていないプログラムの数の比率の確率を見つけます。

コード

#include using namespace std typedef long long ll const int N = 50 + 5 class TeamManagement { private: int n, k int a[N][N], deg[N], canTake[N], isLoyal[N] ll f[N][N][3] public: void dfs(int x, int fa) { // find children vector <int> cd for (int y = 0 y < n y++) if (a[x][y] && y != fa) { dfs(y, x) cd.push_back(y) } int sz = cd.size() if (sz == 0) { // leaf vertex if (isLoyal[x]) { f[x][0][0] = 1, f[x][1][0] = (canTake[x] ? 1 : 0) f[x][0][1] = 1, f[x][1][1] = (canTake[x] ? 1 : 0) f[x][0][2] = 0, f[x][1][2] = (canTake[x] ? 1 : 0) } else { f[x][0][0] = 1, f[x][1][0] = 0 f[x][0][1] = 1, f[x][1][1] = (canTake[x] ? 1 : 0) f[x][0][2] = 0, f[x][1][2] = 0 } return } //Don't take x for (int i = 0 i <= k i++) { if (sz == 1) f[x][i][0] += f[cd[0]][i][0], f[x][i][1] += f[cd[0]][i][0] else { for (int j = 0 j <= i j++) { f[x][i][0] += f[cd[0]][j][0] * f[cd[1]][i - j][0], f[x][i][1] += f[cd[0]][j][0] * f[cd[1]][i - j][0] } } } // Take x if (!canTake[x]) return for (int i = 1 i <= k i++) for (int typ = 0 typ <= 2 typ++) if (typ == 1 || isLoyal[x]) { if (sz == 1) f[x][i][typ] += f[cd[0]][i - 1][1] else for (int j = 0 j < i j++) f[x][i][typ] += f[cd[0]][j][1] * f[cd[1]][i - j - 1][1] } else { if (sz == 1) f[x][i][typ] += f[cd[0]][i - 1][2] else for (int j = 0 j < i j++) f[x][i][typ] += f[cd[0]][j][1] * f[cd[1]][i - j - 1][2] + f[cd[0]][j][2] * f[cd[1]][i - j - 1][1] - f[cd[0]][j][2] * f[cd[1]][i - j - 1][2] } } vector <double> getDistribution (int _n, int _k, vector <string> friends, string loyal) { n = _n, k = _k for (int i = 0 i < n i++) isLoyal[i] = (loyal[i] == 'Y') for (int i = 0 i < n - 1 i++) { istringstream sin(friends[i]) int x, y sin >> x >> y a[x][y] = a[y][x] = 1 deg[x]++, deg[y]++ } int rt = 0 while (deg[rt] > 1) rt++ //Take a leaf as a root memset(canTake, 1, sizeof(canTake)) memset(f, 0, sizeof(f)) vector <double> ans dfs(rt, -1) ll tot = f[rt][k][0] for (int i = 0 i < n i++) { memset(f, 0, sizeof(f)) canTake[i] = 0 dfs(rt, -1) canTake[i] = 1 ans.push_back(1.0 - (f[rt][k][0] * 1.0 / tot)) } return ans } }Solve