複数のアプローチ

一つの問題には複数のアプローチがあることを改めて学びました。一つの問題に時間をかけて取り組むことは大事。

下の問題にチャレンジしましょう。

国王が、秘書に頼んでN人の大臣に個人宛の手紙をくばりました。しかし、ドジな秘書はそれに気付かずにランダムに手紙を配ってしまいました。秘書は、自分のミスに気付いてK人の大臣に、「受け取った手紙は宛先が適切か？」と聞きましたが、全員違うと答えました。秘書が配った手紙の配り方のパターン数を求めなさい。

数学的な問題に帰着すると、以下のようになります。

A1, A2, ..., Anという数列がある。この数列は、Ai != i, i=1,2,...,kを満たす。このような数列のパターンは何パターンあるか？

元ネタ：　http://www.topcoder.com/stat?c=problem_statement&pm=10875

Approach 1:

ビットDPで解く。i = 1, ..,kまではAi != iの縛りがあります。1からkまでの間でどの値が使用されたかを記憶してDPをすればいいです。これは考察はそれほどいらないけど、実装が重いです。

view plainprint?

1. #define MOD 1000000007LL  
2. LL dp[15][1<<15];  
3. LL fact[1024];  
4.   
5. class CarelessSecretary {  
6. public:  
7.     int howMany(int N, int K) {  
8.         fact[0] = 1;  
9.         for (int i = 1; i < 1024; i++)  
10.             fact[i] = i * fact[i-1] % MOD;  
11.   
12.         memset(dp, 0, sizeof(dp));  
13.   
14.         dp[0][0] = 1LL;  
15.         for (int i = 0; i < K; i++) {  
16.             for (int mask = 0; mask < (1<<K); mask++) {  
17.                 if (!dp[i][mask]) continue;  
18.                 for (int j = 0; j < K; j++) {  
19.                     if (j == i) continue;  
20.                     if (mask >> j & 1)  
21.                         continue;  
22.                     dp[i+1][(1<<j)|mask] = (dp[i+1][(1<<j)|mask] + dp[i][mask]) % MOD;  
23.                 }  
24.   
25.                 int rm = N - K - (i - __builtin_popcount(mask));  
26.                 dp[i+1][mask] = (dp[i+1][mask] + rm * dp[i][mask]) % MOD;  
27.             }  
28.         }  
29.   
30.         LL ret = 0;  
31.         for (int mask = 0; mask < (1<<K); mask++) {  
32.             LL patr = fact[N-K] * dp[K][mask] % MOD;  
33.             ret = (ret + patr) % MOD;  
34.         }  
35.   
36.         return (int)(ret % MOD);  
37.     }  
38. };  

#define MOD 1000000007LL
LL dp[15][1<<15];
LL fact[1024];

class CarelessSecretary {
public:
    int howMany(int N, int K) {
        fact[0] = 1;
        for (int i = 1; i < 1024; i++)
            fact[i] = i * fact[i-1] % MOD;

        memset(dp, 0, sizeof(dp));

        dp[0][0] = 1LL;
        for (int i = 0; i < K; i++) {
            for (int mask = 0; mask < (1<<K); mask++) {
                if (!dp[i][mask]) continue;
                for (int j = 0; j < K; j++) {
                    if (j == i) continue;
                    if (mask >> j & 1)
                        continue;
                    dp[i+1][(1<<j)|mask] = (dp[i+1][(1<<j)|mask] + dp[i][mask]) % MOD;
                }

                int rm = N - K - (i - __builtin_popcount(mask));
                dp[i+1][mask] = (dp[i+1][mask] + rm * dp[i][mask]) % MOD;
            }
        }

        LL ret = 0;
        for (int mask = 0; mask < (1<<K); mask++) {
            LL patr = fact[N-K] * dp[K][mask] % MOD;
            ret = (ret + patr) % MOD;
        }

        return (int)(ret % MOD);
    }
};

Approach 2:

Editorial解法。4パターンに分解します。動的計画の式の立て方を勉強する良い例題だと思います。これおは実装は軽いけど、なかなか思いつかないです。あと、場合分けや特殊ケースの処理でミスコーディングする可能性が高いです。

view plainprint?

1. LL ans[1024][16];  
2.   
3. class CarelessSecretary {  
4. public:  
5.     int howMany(int N, int K) {  
6.         for (int i = 0; i <= N; i++) for (int j = 0; j <= K; j++) {  
7.             if (i == 0 && j == 0) ans[i][j] = 1LL;  
8.             else if (i == 0) ans[i][j] = 0LL;  
9.             else if (j == 0) ans[i][j] = i*ans[i-1][j] % MOD;  
10.             else ans [i][j] = ((i-j)*(ans[i-2][j-1] + ans[i-1][j]) + (j-1)*(ans[i-2][j-2] + ans[i-1][j-1]))%MOD;  
11.         }  
12.   
13.       return (int)ans[N][K];  
14.     }  
15. };  

LL ans[1024][16];

class CarelessSecretary {
public:
    int howMany(int N, int K) {
        for (int i = 0; i <= N; i++) for (int j = 0; j <= K; j++) {
            if (i == 0 && j == 0) ans[i][j] = 1LL;
            else if (i == 0) ans[i][j] = 0LL;
            else if (j == 0) ans[i][j] = i*ans[i-1][j] % MOD;
            else ans [i][j] = ((i-j)*(ans[i-2][j-1] + ans[i-1][j]) + (j-1)*(ans[i-2][j-2] + ans[i-1][j-1]))%MOD;
        }

      return (int)ans[N][K];
    }
};

Approach 3:

rng解。ぱない。i=1,..,kまでは1つも被らない。を逆から見て、少なくとも1つは被っているパターン数を包除原理を使って数えています。実装も軽いし、言われてみると確かにこの発想はありかなという感じです。ミスコーディングの可能性の低さからも、この解法がベストだと思います。

view plainprint?

1. #define MOD 1000000007LL  
2.   
3. class CarelessSecretary {  
4. public:  
5.     int howMany(int N, int K) {  
6.         LL F[1024];  
7.   
8.         F[0] = 1;  
9.         FOR (i, 1, 1024) F[i] = i * F[i-1] % MOD;  
10.   
11.         LL ret = 0LL;  
12.         REP(ptrn, 1<<K) {  
13.             int c = __builtin_popcount(ptrn);  
14.             if (c % 2)  
15.                 ret = (ret - F[N-c] + MOD) % MOD;  
16.             else  
17.                 ret = (ret + F[N-c]) % MOD;  
18.         }  
19.   
20.         return (int)ret;  
21.     }  
22. };  

#define MOD 1000000007LL

class CarelessSecretary {
public:
    int howMany(int N, int K) {
        LL F[1024];

        F[0] = 1;
        FOR (i, 1, 1024) F[i] = i * F[i-1] % MOD;

        LL ret = 0LL;
        REP(ptrn, 1<<K) {
            int c = __builtin_popcount(ptrn);
            if (c % 2)
                ret = (ret - F[N-c] + MOD) % MOD;
            else
                ret = (ret + F[N-c]) % MOD;
        }

        return (int)ret;
    }
};