SRM 663 Div2 Hard CheeseRolling

TopCoder Statistics - Problem Statement

• 復習。解き方がさっぱりわからず SRM 663 div2 hard:CheeseRolling - mayoko’s diary を見て解いた。kmjp 先生然り、日本語の解説ページは色々助かる。
• 解法理解するのに時間がかかった。
• それにしても、みんなよくこんなの解けるな...。
• 下のコードの comb あたりのコードは蟻本にのっていたやつ。(どうしてこれでうまく行くのかは正直知らない。)
• ビットによるグループ分割だと同じグループで場所を入れ替えたケースとか計算されてなくね？って思ったがそんなことはなかった。(下コメントの "S の 1bit は S1 にも.." ってあたりの話)

class CheeseRolling {
public:
vector<long long> waysToWin(vector <string> wins) {
        int N = wins.size();
        //
        // 各 i に対して i がトーナメントで優勝できるようなトーナメントの組み合わせを求める
        // 全探索すると n! 通りになる
        //
        // そこで以下のようなアルゴリズムを使う
        // S = {0,...,N-1} を S1,S2 に 2 分割する
        // S1 での優勝者は S2 の優勝者に勝てるとき S で優勝できる
        // よって再帰的分割・統合をくりかえしていけばよい。
        //
        vector<vector<ll>> dp((1<<N), vector<ll>(N,-1));
        function<void(int,int)> dfs = [&](int n, int S) {
            if (n == 1)
            {
                REP(i,N)
                {
                    if ( S & (1<<i) )
                        dp[S][i] = 1;
                    else
                        dp[S][i] = 0;
                }
                return;
            }
            if (dp[S][0] >= 0)  // すでに計算済みなら終了(memo化)
                return;

            fill(RANGE(dp[S]), 0);
            int k = n/2;
            int comb = (1<<k)-1;    // S の 1 ビット集合のサイズ k の部分集合
            while ( comb < (1<<n) ) // 長さ k のビット部分集合 comb ごとにループする
            {
                // S を2つに分割する
                int S1 = 0;
                int S2 = 0;
                int l = 0;
                REP(i, N)
                {
                    if ((1<<i) & S)
                    {
                        if (comb & (1<<l))
                            S1 |= (1<<i);
                        else
                            S2 |= (1<<i);
                        ++l;
                    }
                }
                dfs(k,S1);
                dfs(k,S2);

                vector<int> ai;
                vector<int> bi;
                // index 振り分け
                REP(i, N)
                {
                    if ( S1 & (1<<i) )
                        ai.push_back(i);
                    else if ( S2 & (1<<i) )
                        bi.push_back(i);
                }
                assert(ai.size()==bi.size() && k == ai.size());
                // S1 の優勝者と S2 の優勝者とを比較
                REP(i, k)
                REP(j, k)
                {
                    int ii = ai[i];
                    int jj = bi[j];
                    // S の 1bit は S1 にも S2 にも振り分けられるので
                    // <--S1-->
                    // 1,2,3,4,...
                    // 2,1,3,4,...
                    // のようにグループに所属する i が同じでも場所を変えたケースも
                    // ちゃんと計算されている。
                    if (wins[ii][jj] == 'Y')
                        dp[S][ii] += dp[S1][ii]*dp[S2][jj];
                    if (wins[jj][ii] == 'Y')
                        dp[S][jj] += dp[S1][ii]*dp[S2][jj];
                }

                int x = comb & -comb;
                int y = comb + x;
                comb = (((comb & ~y) / x) >> 1) | y;
            }
            return;
        };
        dfs(N,(1<<N)-1);
        vector<ll> ans;
        REP(i,N)
            ans.push_back(dp[(1<<N)-1][i]);
        return ans;
}
};