fork download
copy 
  1. // original:
  2. //   Myth5's solution to Google Code Jam 2013 Round 1A C. Good Luck
  3. //   http://w...content-available-to-author-only...o.net/jam/13/name/Myth5
  4.  
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>
  8. #include <cmath>
  9. #include <set>
  10. #include <map>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <algorithm>
  15. using namespace std;
  16.  
  17. const int maxn = 12 + 5, maxk = 12 + 5;
  18.  
  19. int R, N, M, K;
  20. long long p[maxk], jc[maxn];
  21. char a[maxn];
  22.  
  23. // 問題
  24. // 2からMまでの数字がかかれたカードの中から、等確率でN枚のカードを選ぶ
  25. // 以下のことをK回繰り返す
  26. //   - N枚のカードのそれぞれを0.5の確率で取り出したサブセットを作る
  27. //   - サブセットに含まれるカードの数字の積を書き出す
  28. // N, Mと数字の積から、N枚のカードの数字が何だったかを当てる
  29.  
  30. //              small  large
  31. //        R      100   8000
  32. //        N        3     12
  33. //        M        5      8
  34. //        K        7     12
  35.  
  36.  
  37. // カードの選び方に関する構造体
  38. // a: カードの選び方　(eg. [2, 2, 2, 3, 3, 4, 4])
  39. // rep: このカードの選び方の確率を計算するときに使う値。(2の枚数)! * ... * (Mの枚数)!で計算される
  40. //     直感的に、同じ数字のカードが多い = repの数が大きい = 確率低い
  41. // P: サブセットの積と、その確率をテーブルで保持
  42. // check(): 観測されたサブセットの積がp[]に格納されている時、Pr( サブセットの積 | カードの選び方 )を計算
  43. struct Sol {
  44.     string a;
  45.     long long rep;
  46.     map<long long, int> P;
  47.     double check()
  48.     {
  49.         double ret = 1;
  50.         for (int i = 1; i <= K; ++i) {
  51.             map<long long, int>::iterator it = P.find(p[i]);
  52.             if (it == P.end())
  53.                 return 0;
  54.             ret *= it->second;
  55.         }
  56.         return ret / rep;
  57.     }
  58.  
  59.     void print(){
  60.         cout << "-----" << endl;
  61.         cout << "a = " << a << endl;
  62.         cout << "rep = " << rep << endl;
  63.         cout << "P = " << endl;
  64.         for(map<long long, int>::iterator it = P.begin();
  65.             it != P.end();
  66.             ++it){
  67.             cout << "   key: " << it->first << ", val: " << it->second << endl;
  68.         }
  69.         cout << "-----" << endl;
  70.     }
  71. };
  72. vector<Sol> v;
  73.  
  74. // すべてのカードの選び方をdfsで求める
  75. void dfs(int i)
  76. {
  77.     if (i == N) {
  78.         // あるカードの選び方が見つかった
  79.         Sol t;
  80.         t.a = string(a);
  81.         //cout << a << endl;
  82.         t.rep = 1;
  83.         for (int j = 0, k = -1; j < N; ++j)
  84.             if (a[j] != a[j + 1]) {
  85.                 t.rep *= jc[j - k];
  86.                 k = j;
  87.             }
  88.  
  89.         // すべてのとりうるサブセットをシミュレーション
  90.         for (int j = 0; j < (1 << N); ++j) {
  91.             long long pro = 1;
  92.             for (int k = 0; k < N; ++k)
  93.                 if (j & (1 << k))
  94.                     pro *= a[k] - '0';
  95.             ++t.P[pro];
  96.         }
  97.         v.push_back(t);
  98.  
  99.  
  100.         // t.print();
  101.  
  102.     }else
  103.         //cout << "i = " << i << endl;
  104.         for (char j = i > 0 ? a[i - 1] : '2'; j <= '0' + M; ++j) {
  105.             //cout << "  j = " << j << endl;
  106.             a[i] = j;
  107.             dfs(i + 1);
  108.         }
  109. }
  110.  
  111. int main()
  112. {
  113.     // freopen("c2.in", "r", stdin);
  114.     // freopen("c2.out", "w", stdout);
  115.  
  116.     int t2;
  117.     cin >> t2;
  118.     for (int t1 = 1; t1 <= t2; ++t1) {
  119.         printf("Case #%d:\n", t1);
  120.         cin >> R >> N >> M >> K;
  121.         jc[0] = 1;
  122.         for (int i = 1; i <= N; ++i)
  123.             jc[i] = jc[i - 1] * i;
  124.         a[N] = '\0';
  125.         dfs(0);
  126.         while (R--) {
  127.             for (int i = 1; i <= K; ++i)
  128.                 cin >> p[i];
  129.             double ret = 0;
  130.             int reti = 0;
  131.             for (int i = 0; i < v.size(); ++i) {
  132.                 double t = v[i].check();
  133.                 if (t > ret) {
  134.                     ret = t;
  135.                     reti = i;
  136.                 }
  137.             }
  138.             cout << v[reti].a << endl;
  139.         }
  140.         printf("\n");
  141.     }
  142.  
  143.     return 0;
  144. }
  145.  
Success #stdin #stdout 0s 3040KB
comments (?)
stdin
copy 
1
1 2 5 3
4 4 1
stdout
copy 
Case #1:
44
https://ideone.com/USU3tI
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!