問題的陳述在：https://code.google.com/codejam/contest/2418487/dashboard#s=p2&a=1，

官方的分析在：https://code.google.com/codejam/contest/2418487/dashboard#s=a&a=2。

這篇文章是結(jié)合官方的分析以及Dlougach的solution總結(jié)的解題思路。

1. 列舉所有的可能的數(shù)字組合

由[2,M]區(qū)間內(nèi)的數(shù)字組成長度為N的數(shù)組組合，本身有(M-1)^N可能性，因為組合中的每一個數(shù)字都可以從[2,M]這M-1個數(shù)字中隨機選取。

但是由于這些數(shù)字組合本身不存在順序的問題，比如（5, 2, 3, 2）和（2, 2, 3, 5）是相同的，所以可以排除掉很多相同的情況。

可以編程列舉出所有的數(shù)字組合，思路是從N個2的數(shù)字組合開始，順序加1，直到N個M的組合。代碼如下：

1 // all possible combinations 2 vector<vector<int>> digits; 3 vector<int> dig(N, 2); 4 while (dig != vector<int>(N, M)) 5 { 6 digits.push_back(dig); 7 int i = N-1; 8 while (dig[i] == M) i--; 9 dig[i]++; 10 for (int j = i + 1; j < N; j++) 11 dig[j] = dig[i]; 12 } 13 digits.push_back(dig); 14 int total = digits.size();

經(jīng)過所有的列舉，共有18564種可能的數(shù)字組合。

2. 計算每一種數(shù)字組合出現(xiàn)的概率。

當給出的所有的K個products都為1的時候應(yīng)該選擇哪一個數(shù)字組合呢？選擇N個2還是其他？

要注意到，即便給出的所有K個products都為1，由于每一種數(shù)字組合出現(xiàn)的概率也有區(qū)別，也可以從中選取出可能出現(xiàn)概率最高的數(shù)字組合。

對于一個數(shù)字組合，計算這個數(shù)字組合可能出現(xiàn)的概率：

比如M = 8, N = 12的情況下，222333445558出現(xiàn)的可能性為：(C(12,3)*C(9,3)*C(6,2)*C(4,3)*C(1,1)) / (8-1)¹²，即在所有的12個位置中找3個位置擺放2，再在剩下的9個位置中找3個位置擺放3，再在剩下的6個位置中找2個位置擺放4.....最后除以總數(shù)(8-1)¹²。

其中C(n,k)就是我們在學概率時學到的C_n^k。

所以要想求概率，首先需要統(tǒng)計出每個數(shù)字重復出現(xiàn)的次數(shù)，具體代碼如下：

1 vector<double> prob(total, 0); 2 for (int i = 0; i < total; ++i) 3 { 4 vector<int> count(M+1, 0); 5 for (int j = 0; j < N; ++j) 6 count[digits[i][j]]++; 7 double p = 0; 8 int size = N; 9 for (int j = 2; j <= M; ++j) 10 { 11 p += log(C[size][count[j]]); 12 size -= count[j]; 13 } 14 prob[i] = p; 15 }

這段代碼中有兩點技巧：一是C(n,k)的計算方法，二是取對數(shù)(log)問題。

a) C(n,k)的計算

C(n,k)本身有一個計算公式是我們很熟悉的：C(n,k) = n! / (k!(n-k)!)。這樣計算牽涉到階乘，考慮到要計算多個C(n,k)，為了重復利用計算好的結(jié)果，這里有一個比較簡單的方法，就是楊輝三角型(Pascal's triangle)以及。

首先構(gòu)建一個楊輝三角形存放于二維數(shù)組C中，如下圖所示。這樣的擺放有一個規(guī)律C[n][m] = C[n-1][m-1]+C[n-1][m]，恰好是C(n,k)的另一種計算方法。

? ? ? ? ? ? ? m?= 0 ? ?m?= 1 ? ?m?= 2 ? ?m?= 3 ? ?m?= 4 ? ?m?= 5...

n?= 0 ? ? ? ? ?1 ? ? ? ? ? 0 ? ? ? ? ? 0 ? ? ? ? ? ?0 ? ? ? ? ? 0 ? ? ? ? ? 0...

n?= 1 ? ? ? ? ?1 ? ? ? ? ? 1 ? ? ? ? ? 0 ? ? ? ? ? ?0 ? ? ? ? ? 0 ? ? ? ? ? 0...

n?= 2 ? ? ? ? ?1 ? ? ? ? ? 2 ? ? ? ? ? 1 ? ? ? ? ? ?0 ? ? ? ? ? 0 ? ? ? ? ? 0...

n?= 3 ? ? ? ? ?1 ? ? ? ? ? 3 ? ? ? ? ? 3 ? ? ? ? ? ?1 ? ? ? ? ? 0 ? ? ? ? ? 0...

n?= 4 ? ? ? ? ?1 ? ? ? ? ? 4 ? ? ? ? ? 6 ? ? ? ? ? ?4 ? ? ? ? ? 1 ? ? ? ? ? 0...

這樣一來只要提取數(shù)組元素C[n][k]，就是C(n,k)的值，比如C(4,2) = C[4][2] = 6。數(shù)組搭建過程實現(xiàn)如下：

1 double C[13][13]; 2 memset(C, 0, sizeof(C)); 3 C[0][0] = 1; 4 for (int i = 1; i < 13; ++i) 5 { 6 C[i][0] = 1; 7 for (int j = 1; j <= i; ++j) 8 C[i][j] = C[i-1][j-1] + C[i-1][j]; 9 }

b)?取對數(shù)(log)問題

對數(shù)運算有一個性質(zhì)：log(ABC...Z)=log(A)+log(B)+log(C)...log(Z)。

如果要比較幾個元素的大小（所有元素都大于0），并且每個元素都由多個數(shù)的乘積構(gòu)成，則可以簡化為判斷所有元素對數(shù)的大小（取對數(shù)不會影響增減性），這樣一來對于每個元素來講，并不需要計算多個數(shù)的乘法了，而是這些數(shù)取對數(shù)之后的加法。

這樣計算有一個很大的好處，就是乘法運算本身很容易導致結(jié)果溢出，取對數(shù)變加法之后可以避免溢出，并且大大減小運算范圍。

3. 對于每一種數(shù)字組合，列舉所有可能出現(xiàn)的products，并對其進行計數(shù)

用一個mask，從1到1<<N遍歷一遍，mask的二進制為1的相應(yīng)位將參與product計算。比如mask為21，二進制表示為10101，那么該數(shù)字組合中，將從右數(shù)起的第1、3、5個數(shù)字相乘得到product。

1 vector<unordered_map<long long, int>> products(total); 2 for (int i = 0; i < total; ++i) 3 { 4 for (int mask = 1; mask < (1<<N); ++mask) 5 { 6 long long prod = 1; 7 for (int j = 0; j < N; ++j) 8 if (mask & (1<<j)) 9 prod *= digits[i][j]; 10 products[i][prod] += 1; 11 } 12 }

以上三步都是進行pre-computation，下面就是真正運行測試數(shù)據(jù)了。

4. 遍歷每一種數(shù)字組合，計算該數(shù)字組合出現(xiàn)的概率，最后選取概率最高者輸出。?

給定product 1, 2, 3, ..., K的情況下，數(shù)字組合A出現(xiàn)的概率p(A) = A本身出現(xiàn)的概率prob[A] * product 1出現(xiàn)的概率products[A][product1] * .... * product K出現(xiàn)的概率products[A][product K]。

由于這些算好的概率都已經(jīng)取號對數(shù)，所以應(yīng)該用加法。

1 while (R--) 2 { 3 vector<int> test_products; 4 for (int i = 0; i < K; ++i) 5 test_products.push_back(rll()); 6 int res_i = 0; 7 double resProb = INT_MIN; 8 for (int i = 0; i < total; ++i) 9 { 10 double p = prob[i]; 11 for (int k = 0; k < K; ++k) 12 { 13 if (test_products[k] == 1) break; 14 unordered_map<long long, int>::iterator it = products[i].find(test_products[k]); 15 if (it != products[i].end()) 16 { 17 p += log((double)it->second); 18 } 19 else 20 { 21 p = INT_MIN; 22 break; 23 } 24 } 25 if (resProb < p) 26 { 27 res_i = i; 28 resProb = p; 29 } 30 } 31 for (int i = 0; i < digits[res_i].size(); ++i) 32 printf("%d", digits[res_i][i]); 33 printf("\n"); 34 }

這道題完整的代碼可以在下面的鏈接獲取：https://github.com/AnnieKim/ForMyBlog/blob/master/20130508/1A-C-Good%20Luck.cpp

原創(chuàng)文章，轉(zhuǎn)載請注明出處：http://www.cnblogs.com/AnnieKim/archive/2013/05/08/3059614.html。

轉(zhuǎn)載于:https://www.cnblogs.com/AnnieKim/archive/2013/05/08/3059614.html

總結(jié)

以上是生活随笔為你收集整理的[Google Code Jam] 2013-1A-C Good Luck 解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。