SRM 663 div2 hard:CheeseRolling

yukiさんが青コーダーなった記念にyukiさんの動画を覗きに行ったら問題の紹介をしていたので解くことにしました。結構苦戦したしdiv2 hardも練習しても良さそう。

問題

TopCoder Statistics - Problem Statement

解法

ある集合stateの中である人nがどれだけ優勝するかをdp[state][n]でメモしていきます。

stateを2つに分けて(s1, s2とする),それぞれをdfsで計算します。で,ある人nがs1で優勝した際にs2で優勝した人に勝つ回数は〜みたいな感じでやっていけば解けます。

int N;
ll dp[1<<16][16];
vector<string> wins;

void dfs(int n, int state) {
    if (n == 1) {
        for (int i = 0; i < N; i++) {
            if ((state>>i)&1) dp[state][i] = 1;
            else dp[state][i] = 0;
        }
        return;
    }
    if (dp[state][0] >= 0) return;
    for (int i = 0; i < N; i++) dp[state][i] = 0;
    int to[n];
    int k = 0;
    for (int i = 0; i < N; i++) if ((state>>i)&1) to[k++] = i;
    for (int s = 0; s < (1<<n); s++) {
        int cnt = __builtin_popcount(s);
        if (cnt != n/2) continue;
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n; i++) {
            if ((state>>to[i])&1) {
                if ((s>>i)&1) s1 |= (1<<to[i]);
                else s2 |= (1<<to[i]);
            }
        }
        dfs(n/2, s1);
        dfs(n/2, s2);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (wins[to[i]][to[j]] == 'Y') {
                    dp[state][to[i]] += dp[s1][to[i]] * dp[s2][to[j]];
                    dp[state][to[i]] += dp[s2][to[i]] * dp[s1][to[j]];
                }
            }
        }
    }
}

class CheeseRolling {
public:
    vector<long long> waysToWin(vector <string> wins) {
        ::wins = wins;
        memset(dp, -1, sizeof(dp));
        N = wins.size();
        dfs(N, (1<<N)-1);
        vector<ll> ans(N);
        for (int i = 0; i < N; i++) ans[i] = dp[(1<<N)-1][i];
        return ans;
    }
};