SRM537 Div2 Hard

925
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で１、最大でルートまでの距離
全ての頂点に関して試す。

点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。

view plainprint?

1. class PrinceXToastbook {  
2. public:  
3.   double eat(vector <int> P)  
4.   {  
5.     const int N = P.size();  
6.     bool vis[N];  
7.   
8.     vector<double> v[N];  
9.      
10.     for (int i = 0, j; i < N; ++i) {  
11.       fill(vis, vis + N, false);  
12.       double depth = 1;  
13.       for (j = i; P[j] != -1; j = P[j]) {  
14.         if (vis[j]) {  
15.           depth = 0;  
16.           break;  
17.         }  
18.         ++depth;  
19.         vis[j] = true;  
20.       }  
21.       if (depth) v[j].push_back(depth);  
22.     }  
23.   
24.     double ret = 0;  
25.     for (int i = 0; i < N; ++i) {  
26.       if (v[i].empty()) continue;  
27.       for (int j = 0; j < v[i].size(); ++j) {  
28.         double n = 1.0;  
29.         for (int k = 1; k <= v[i][j]; ++k) {  
30.           n /= k;  
31.         }  
32.         ret += n;  
33.       }  
34.     }  
35.     return ret;  
36.   }  
37. };  

class PrinceXToastbook {
public:
  double eat(vector <int> P)
  {
    const int N = P.size();
    bool vis[N];

    vector<double> v[N];
   
    for (int i = 0, j; i < N; ++i) {
      fill(vis, vis + N, false);
      double depth = 1;
      for (j = i; P[j] != -1; j = P[j]) {
        if (vis[j]) {
          depth = 0;
          break;
        }
        ++depth;
        vis[j] = true;
      }
      if (depth) v[j].push_back(depth);
    }

    double ret = 0;
    for (int i = 0; i < N; ++i) {
      if (v[i].empty()) continue;
      for (int j = 0; j < v[i].size(); ++j) {
        double n = 1.0;
        for (int k = 1; k <= v[i][j]; ++k) {
          n /= k;
        }
        ret += n;
      }
    }
    return ret;
  }
};