SRM 660 div1 med:Privateparty

問題

TopCoder Statistics - Problem Statement

解法

適当に実験してるとなんか漸化式が出てくるのでそれで解いても良い。…が,どうもしっくりこないのでDPを使ってちゃんと解いてみる。

まず前提となる考え方から。
ある人aに嫌いな人がいて,さらにその嫌いな人にも嫌いな人がいて,...という関係があるとすると,aの人が影響を受ける人は,その嫌いな人の列すべてに対してになります。それを上手く処理するために,dpを考えるわけです。

ということで本番。
dp[n][x]を(n人に影響を受ける人がx番目にACされる確率)とします。すると,n人に影響される人がACされる確率は
dp[n][1] + dp[n][2] + ... dp[n][n]となります。

ということでdp[n][x]を求めることができたら勝ちです。
まず,この人の嫌いな人がx番目より後に来る場合(確率は)は絶対にACされます。
次に,先に嫌いな人が入場しようとする場合は,その嫌いな人がy番目に入場する(その確率は)とすると,その人はWAでないといけません。その確率は1-dp[n-1][y]です。

これを用いて漸化式を立てることが出来ます。

適当に見つけた漸化式編

int n;
int G[55];
double pp[55];
bool vis[55];

class Privateparty {
public:
    double getexp(vector <int> a) {
        pp[1] = 1, pp[2] = 0.5;
        for (int i = 3; i < 55; i++) {
            pp[i] = pp[i-2]/i + pp[i-1]*(i-1)/(1.*i);
        }
        n = a.size();
        double ret = 0;
        for (int i = 0; i < n; i++) G[i] = a[i];
        for (int i = 0; i < n; i++) {
            int cnt = 0, cur = i;
            memset(vis, false, sizeof(vis));
            while (1) {
                if (vis[cur]) {
                    break;
                }
                vis[cur] = true;
                cnt++;
                if (cur == G[cur]) break;
                cur = G[cur];
            }
            ret += pp[cnt];
        }
        return ret;
    }
};

DP編

double dp[55][55];
double sum[55];

class Privateparty {
public:
    double getexp(vector <int> a) {
        for (int i = 0; i < 55; i++) for (int j = 0; j < 55; j++) {
            dp[i][j] = 0;
            sum[i] = 0;
        }
        dp[1][1] = 1;
        for (int n = 2; n < 55; n++) {
            for (int x = 1; x <= n; x++) {
                dp[n][x] += 1.*(n-x) / (n-1);
                for (int y = 1; y < x; y++) {
                    dp[n][x] += 1./(n-1) * (1-dp[n-1][y]);
                }
            }
        }
        for (int i = 1; i < 55; i++) {
            for (int j = 0; j < 55; j++) {
                sum[i] += dp[i][j] / i;
            }
        }
        int n = a.size();
        double ret = 0;
        bool vis[55];
        for (int i = 0; i < n; i++) {
            if (a[i] == i) {
                ret += 1;
                continue;
            }
            memset(vis, false, sizeof(vis));
            vis[i] = true;
            int cur = a[i];
            int cnt = 1;
            while (1) {
                if (vis[cur]) break;
                cnt++;
                vis[cur] = true;
                if (cur == a[cur]) break;
                cur = a[cur];
            }
            ret += sum[cnt];
        }
        return ret;
    }
};